On a unique tree representation for \(P_ 4\)-extendible graphs (Q1182318)

A \(P_ 4\) of some simple finite graph \(G\) is an induced simple path subgraph of \(G\) with 4 nodes. \(G\) is \(P_ 4\)-extendible if for any subset \(W\) of \(G\), which contains some \(P_ 4\), there exists at most one external node \(x\), such that \(x\) forms a \(P_ 4\) together with vertices of \(W\). These include all cographs (graphs without \(P_ 4)\) and \(P_ 4\)-reducible graphs (in which all \(P_ 4\)'s are node-disjoint). A tree representation of a graph \(G\) is a binary tree of graphs, with root \(G\) and leaves of some specified type (here single node graphs), where each nonleave-node is obtained from its sons by some simple graph operation. A constructive characterization of \(P_ 4\)-extendible graphs is obtained, showing that any such graph \(G\) may be obtained from a set of singleton node graphs by way of four different graph operations. This leads to a unique (up to isomorphism) tree representation of \(G\), with singleton leaves and using the four graph operations above, which can be constructed in polynomial time. It follows that the graph isomorphism problem is polynomially solvable for \(P_ 4\)-extendible graphs. It is conjectured that a linear time recognition algorithm for \(P_ 4\)- extendible graphs exists, as is known to be the case for cographs and \(P_ 4\)-reducible graphs.