On cocolourings and cochromatic numbers of graphs (Q1315460)

A cocolouring of a graph \(G\) is a partition of the vertices such that each set of the partition induces either a clique or an independent set in \(G\). The cochromatic number \(z(G)\) is the smallest cardinality of a cocolouring of \(G\). Given a graph \(G\) and an integer \(k\), the cochromatic number problem, i.e., determine if \(z(G) \leq k\), is known to be NP- complete. Here the authors show that it remains NP-complete for line graphs of comparability graphs and present polynomial time algorithms for computing the cochromatic number of chordal graphs and graphs containing no induced \(P_ 4\).