The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.
Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ It can be easily shown that $\alpha(G) \geq \frac{n(G)}{\chi(G)}$, where $\alpha(G)$ is the independent set size of the graph. Since finding maximum independent set is hard, seems like finding the chromatic number should also be hard. $\endgroup$– Vivek BagariaMay 3, 2014 at 17:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
They can be 3-colored in polynomial time, no? I didn't check the literature but here is a simple approach: take a DFS tree of the graph and color a node $u$ at depth $d(u)$ with color $(d(u)\mod 3)$. This gives a proper coloring since (1) the neighborhood of each vertex is an independent and (2) two nodes $u,v$ such that $|d(u)-d(v)| \geq 2$ cannot be adjacent.
-
1$\begingroup$ It is NP-Complete to find $\chi(G)$ for triangle-free graphs. Mentioned here, konrad127123.s3-website-eu-west-1.amazonaws.com/… I think your algorithm fails for $C_4$, a cycle of four vertices. $\endgroup$ Apr 12, 2014 at 3:21
-
$\begingroup$ Clearly if you can $c$-color a triangle-free graph in polynomial time then you get a $\frac{c}{3}$-approximation of the chromatic number. So either the problem is indeed NP-complete or my claim is incorrect, but I can't spot the error ?? However, the triangle-free graphs don't seem a very well-behaved class, so I wouldn't be surprised if the problem is NP-complete. $\endgroup$– Super8Apr 12, 2014 at 3:31
-
2$\begingroup$ I do not see why it is a $\frac{c}{3}$-approximation? Are you saying approximation of the chromatic number of any graph, or the triangle-free graph given as input? DFS tree of a $C_4$ is a chain, and your algorithm color it with 1-2-3-1. $\endgroup$ Apr 12, 2014 at 3:39
-
$\begingroup$ Yes, I'm saying that you get a $\lceil \frac{c}{3} \rceil$-approx if the input is triangle-free: either $\chi(G) \leq 2$ and you can color it optimally, or $\chi(G) = 3$ and you get a coloring with $\frac{c}{3} \chi(G)$ colors using the approx. Also, I agree that your counterexample disproves my claim in its current form. $\endgroup$– Super8Apr 12, 2014 at 3:48