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.
