# How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

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 :

1. what is the worst behavior of greedy coloring on cograph coloring?
2. Is it possible that the greedy coloring needs more than $\lceil \frac{1+\Delta}{2} \rceil$ colors?

We can modify this construction to cut down the max degree as well... 4,5,6 are adjacent to 3, but make 7,8,9 still adjacent to 6 but now adjacent to 1 instead of 3. Then make 10,11,12 adjacent to 9, 4(instead of 6), and 3. And for future triplets, keep alternating which end-vertex of a prior P3 they join to. The resulting graph is probably not partitionable into 2 cographs anymore, but observe that 2,5,8,11,etc form an independent set and the rest is probably coverable with 2 more cographs, but I'm not quite sure. But I don't think this is important ... what is important here is that the max degree is low enough that the greedy colouring uses more than $\frac{1+\Delta}{2}$ colours (to answer your second question.)