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

Question

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?

Answer 1

nice question. Consider the following construction: build k P3s numbered / ordered as 1-2-3 4-5-6 7-8-9, etc. Now 1-2-3 all get colour R by the greedy scheme. Make 4,5,6 all adjacent to 3. Then 4,5,6 each get colour B. Now make vertices 7,8,9 adjacent to 3 and to 6, then they can't get colours R or B. They get Y.

Continue with 10-11-12, with 10,11,12 adjacent to 3,6,9. They cannot be coloured with R B Y, so they get G.

These 3k vertices will need k = n/3 colours. But note that c(G) is 2, since the set {3,6,9,12,etc} induce a clique, and the rest of the graph induces a perfect matching. So this shows that greedy colouring can still be arbitrarily bad for cograph colouring as well.

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.)

Another interesting question to ask would be whether a "smarter" greedy colouring (such as LexBFS) would produce a constant-ratio approximation.