A tree representation for \(P_ 4\)-sparse graphs (Q1183332)

A tree-representation for a class \(\Gamma\) of graphs is the association with every graph \(G\in\Gamma\) of a unique rooted tree \(T(G)\), whose leaves are elements of \(G\), and whose internal vertices correspond to certain graph operations. ``If \(T(G)\) can be obtained efficiently ... and if its leaves can be tested efficiently for isomorphism, then the graph isomorphism problem...can be solved efficiently for graphs in \(\Gamma\), since it reduces to tree isomorphism.'' The class of cographs (complement-reducible graphs or \(P_ 4\)-restricted graphs), generated from the single-vertex graph by complementation and union, consists precisely of all graphs having no chordless path on four vertices (a \(P_ 4\)). This class is contained in the class of \(P_ 4\)- reducible graphs, in which no vertex is contained in more than one \(P_ 4\). Unique tree representations have been obtained for these classes. The class of \(P_ 4\)-reducible graphs is contained in the class of \(P_ 4\)-sparse graphs, in which every set of five vertices induces at most one \(P_ 4\). ``We give several characterizations of \(P_ 4\)-sparse graphs, and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the \(P_ 4\)-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time. ... this tree representation can be used to provide efficient solutions to the four classical graph optimization problems: ... finding the largest number \(\omega(G)\) of pairwise adjacent vertices, ... the largest number \(\alpha(G)\) of pairwise adjacent vertices in the complement,'' the chromatic number \(\chi(G)\), and the chromatic number of the complement \(\theta(G)=\chi(\overline G)\). Finally, it is shown that the problem of finding a largest induced \(P_ 4\)-free subgraph is provided by a greedy algorithm in polynomial time.