5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.