Abstract
Cographs form the minimal family of graphs containing K-1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs.
We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function.
We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number.
We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt.
We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity; in particular, that computing the c-chromatic number is NP-complete for planar graphs.