c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-free graph, i.e., there is no induced path of length 3.
The paper denotes the c-chromatic number as $c(G)$ and proves that $c(G)\le \lceil \frac{1+\Delta}{2} \rceil$ in Remark 12 on page 4. The proof can be used to convert any coloring to a coloring of at most $\lceil \frac{1+\Delta}{2} \rceil$ colors, in polynomial time.
In the study of the classic graph coloring, i.e., the chromatic number $\chi(G)$, greedy coloring was discussed. The performance of greedy coloring is determined by the order of vertices. In the worst case, a graph needs $\frac{|V|}{2}$ colors while $\chi(G)=2$. This implies that the approximation ratio of greedy coloring is arbitrarily bad.
Similarly, when we are coloring graph into cographs, we can use the greedy coloring. Given a order of vertices, label each vertex with the smallest color ( assume colors are labeled as 1, 2, 3, ....) such that each color class is a cograph.
My question are :
- what is the worst behavior of greedy coloring on cograph coloring?
- Is it possible that the greedy coloring needs more than $\lceil \frac{1+\Delta}{2} \rceil$ colors?