A graph is P4-connected if, for every partition of its vertices into two nonempty disjoint sets, some P4 in the graph contains vertices from both sets in the partition. A p-tree is a P4-connected graph such that each induced subgraph contains a vertex which belongs to at most one P4. It has been shown that these graphs have numerous tree-like characterizations. In this paper we present linear-time methods to recognize and to test isomorphism of p-trees. Our algorithms are based on new structural results.
