Partitions of graphs into cographs

Cographs   form the minimal family of graphs containing K1K1 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 cc-chromatic number   of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on cc-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 cc-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; namely, there exist triangle-free graphs with arbitrarily large cc-chromatic numbers. We show that any planar graph with girth at least 1111 has a cc-chromatic number at most two. We close with several remarks on computational complexity. In particular, we show that computing the cc-chromatic number is NP-complete for planar graphs.