On the P-4-components of graphs

Two edges are called P-4-adjacent if they belong to the same P-4 (chordless path on four vertices). P-4-components, in our terminology, are the equiva lence classes of the transitive closure of the P-4-adjacency relation. In t his paper, new results on the structure of P-4-components are obtained. On the one hand, these results allow us to improve the complexity of orienting P-4-comparability graphs and of recognizing P-4-indifference graphs from O (n(5)) and O(n(6)) to O(m(2)). On the other hand, by combining the modular decomposition with the substitution of P-4-components, a new unique tree re presentation for arbitrary graphs is derived which generalizes the homogene ous decomposition introduced by Jamison and Olariu (SIAM J. Discrete Math. 8 (1995) 448-463). (C) 2000 Elsevier Science B.V. All rights reserved.