<p>Nice question.
Consider the following construction: build <span class="math-container">$k$</span> <span class="math-container">$P_3$</span>s numbered / ordered as 1-2-3, 4-5-6, 7-8-9, etc.
Now 1-2-3 all get colour <span class="math-container">$R$</span> by the greedy scheme. Make 4,5,6 all adjacent to 3. Then 4,5,6 each get colour <span class="math-container">$B$</span>. Now make vertices 7,8,9 adjacent to 3 and to 6, then they can not get colours <span class="math-container">$R$</span> or <span class="math-container">$B$</span>. They get <span class="math-container">$Y$</span>.</p>
<p>Continue with 10-11-12, with 10,11,12 adjacent to 3,6,9. They cannot be coloured with <span class="math-container">$R, B, Y$</span>, so they get <span class="math-container">$G$</span>.</p>
<p>These <span class="math-container">$3k$</span> vertices will greedily use <span class="math-container">$k = n/3$</span> colours. But note that <span class="math-container">$c(G)$</span> is 2, since the set <span class="math-container">$\{3,6,9,12,\ldots\}$</span> induces 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.</p>
<p>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 <span class="math-container">$\frac{1+\Delta}{2}$</span> colours (to answer your second question.)</p>
<p>Another interesting question to ask would be whether a &quot;smarter&quot; greedy colouring (such as LexBFS) would produce a constant-ratio approximation.</p>

CC BY-SA 4.0
2014-02-19T06:56:29.503Z
2024-01-26T17:47:55.400Z
2024-01-26T17:47:55.400Z
JimN
<p><strong>c-chromatic number</strong> is defined in the paper <a href="http://www.sciencedirect.com/science/article/pii/S1571065304001155">Partitions of graphs into cographs</a>. It asks for the minimum number of colors used to color vertices such that each color class is a <a href="https://en.wikipedia.org/wiki/Cograph">cograph</a>. Cograph is a <strong>P4-free</strong> graph, i.e., there is no induced path of length 3. </p>

<p>The <a href="http://www.sciencedirect.com/science/article/pii/S1571065304001155">paper</a> 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 <em>at most</em> $\lceil \frac{1+\Delta}{2} \rceil$ colors, in polynomial time. </p>

<p>In the study of the classic graph coloring, i.e., the chromatic number $\chi(G)$, <a href="https://en.wikipedia.org/wiki/Greedy_coloring">greedy coloring</a> 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.</p>

<p>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. </p>

<p>My question are :</p>

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

<graph-theory><approximation-algorithms><graph-colouring>
How bad can the greedy coloring (list color) for the c-chromatic number of graph be?
Peng Zhang
# How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

(Asked by: username_0 on 2014-02-19)

**c-chromatic number** is defined in the paper [Partitions of graphs into cographs](http://www.sciencedirect.com/science/article/pii/S1571065304001155). It asks for the minimum number of colors used to color vertices such that each color class is a [cograph](https://en.wikipedia.org/wiki/Cograph). Cograph is a **P4-free** graph, i.e., there is no induced path of length 3.

The [paper](http://www.sciencedirect.com/science/article/pii/S1571065304001155) 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](https://en.wikipedia.org/wiki/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?

**Tags:** graph-theory, approximation-algorithms, graph-colouring

---

## 1 answers

### Answer by username_1 on 2014-02-19. Score: 5 | Accepted answer

Nice question.
Consider the following construction: build $k$ $P\_3$s 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 not 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 greedily use $k = n/3$ colours. But note that $c(G)$ is 2, since the set $\{3,6,9,12,\ldots\}$ induces 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.


---

