Partitions of graphs into cographs (Q607000)

A cograph is a graph that can be constructed by a single vertex using complementation and disjoint union operations. Equivalently, cographs are exactly those graphs which do not contain an induced path \(P_4\) with four vertices and three edges. The \(c\)-chromatic number \(c(G)\) of a graph \(G\) is the minimum number \(k\) such that the vertex set of \(G\) can be partitioned into \(k\) susbsets each of which induces a cograph in \(G\). The authors present several bounds on \(c\)-chromatic number such as {\parindent=7mm \begin{itemize}\item[(i)]\(c(G)=O\left(\frac{n}{\log n}\right)\), \(c(G)=O\left(\frac{\sqrt{m}}{\log m}\right)\), and \(c(G)=O\left(\frac{\sqrt{g}}{\log g}\right)\) for all graphs \(G\) with \(n\) vertices, \(m\) edges, and genus \(g\), \item[(ii)]\(c(G)\leq\lceil\frac{1+\Delta}{2}\rceil\) for all graphs with maximum degree \(\Delta\), and \item[(iii)]\(c(G)\leq \chi(G)\leq 2c(G)\) for all triangle-free graphs \(G\). \end{itemize}} Moreover, they show that the bounds in (iii) are sharp: For all \(k\) and all \(\ell\geq 3\), there exist graphs \(G\) and \(H\) each of girth at least \(\ell\) with \(c(G)=\chi(G)=k\) and \(c(H)= k, \chi(H)=2k\). The authors also discuss the computational complexity of deciding if the \(c\)-chromatic number of a given graph is at most \(k\). They show that (iv) deciding if \(c(G)\leq 2\) is NP-complete for planar graphs \(G\) with maximum degree six, (v) deciding if \(c(G)\leq 3\) is NP-complete for planar graphs \(G\), and (vi) deciding if \(c(G)\leq k\) is NP-complete for any fixed \(k\geq 2\) and all chordal graphs \(G\). It should be remarked that the following similar results have been shown in [\textit{C. T. Hoang} and \textit{V. B. Le}, ``\(P_4\)-colorings and \(P_4\)-bipartite graphs'', Discrete Math. Theor. Comput. Sci. 4, No.\,2, 109--122 (2001; Zbl 0965.05041)]: Deciding if \(c(G)\leq k\) is NP-complete for any fixed \(k\geq 2\) and all comparability graphs \(G\), as well as for all graphs \(G\) without induced \(P_5\). (Note that graphs without induced \(P_4\) have \(c\)-chromatic number one.) The paper poses an interesting open question: Is \(c(G)\leq 2\) for all triangle-free planar graphs \(G\)? The authors show that this is true in case \(G\) has girth at least 11.