Recognition and isomorphism of tree-like \(P_4\)-connected graphs (Q1962050): Difference between revisions

The chordless path on four vertices is denoted by \(P_4\). A graph is \(P_4\)-connected if, for each partition of its vertices into two disjoint parts, there exists a \(P_4\) containing vertices from both parts. A \(p\)-tree is a \(P_4\)-connected graph in which each induced subgraph contains a vertex that belongs to at most one \(P_4\). Although a (\(P_4\)-connected) tree is, in general, not a \(p\)-tree, there are numerous tree-like characterizations of \(p\)-trees; see \textit{L. Babel} [Tree-like \(P_4\)-connected graphs, Discrete Math. 191, No. 1-3, 13-23 (1998)]. The author gives a new characterization of \(p\)-trees (Theorem 5.1) which allows him to recognize \(p\)-trees and to test isomorphism of \(p\)-trees in linear time.