Partitions of graphs into cographs

DOI10.1016/J.DISC.2010.07.011MaRDI QIDQ607000zbMATH OpenOpenAlexWikidataFDO

Publication date 19 November 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2010.07.011

\(P_4\)-free coloring cograph graph coloring

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Partitions of graphs into cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607000)