On the P4-components of graphs

Two edges are called P₄-adjacent if they belong to the same P₄ (chordless path on four vertices). P₄-components, in our terminology, are the equivalence classes of the transitive closure of the P₄-adjacency relation. In this paper, new results on the structure of P₄-components are obtained. On the one hand, these results allow us to improve the complexity of orienting P₄-comparability graphs and of recognizing P₄-indifference graphs from O(n⁵) and O(n⁶) to O(m²). On the other hand, by combining the modular decomposition with the substitution of P₄-components, a new unique tree representation for arbitrary graphs is derived which generalizes the homogeneous decomposition introduced by Jamison and Olariu (SIAM J. Discrete Math. 8 (1995) 448–463).