The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of them is c-chromatic number, $c(G)$, defined in the paper Partitions of graphs into cographs. It asks that each color class is a cograph. Cograph is a P4-free graph, i.e., there is no induced path of length 3.

"G-free-complexity" implies that it is NP-Complete decide $c(G)=k$ for any $k\ge 2$. I have thought following questions about (in-)approximating $c(G)$ for a while. Any suggestion is appreciated. Intuitively, I think these graph coloring are really hard to approximate.

This post is related to a previous one about greedy coloring using a list.

Question 1. Given a graph $G$ of $c(G)=2$, is it hard (e.g., unless P=NP. or any other hardness assumption) to partition $G$ into three cographs? How hard is it to approximate $c(G)$ for general graphs.

Related results of the classic $\chi(G)$. It is hard to 4-color a 3-colorable graph. There are many inapproximateness results from the well-known PCP theorem. I tried to learn this theorem myself but it is hard for me to apply it to get inapproximate result of $c(G)$. I also tried gap amplification technique used to show it is hard to 2-approximate $\chi(G)$ by Garey & Johnsn.

Question 2. How good can we approximate $c(G)$ in polynomial time?

Related results. "Approximate Hypergraph Coloring" shows that, for any 4-uniform 2-colorable hypergraph $H$, there is a randomized algorithm to color $H$ using $O(n^{2/9}\log n)$ colors. For any graph, Remark 12 shows that we can partition $G$ into at most $\lceil \frac{\Delta + 1}{2} \rceil $ cographs.

Any suggestion is welcome. A good tutorial or note of PCP Theorem (including application) is great. Thank you very much.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.