5
$\begingroup$

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?

$\endgroup$
  • $\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 Bagaria May 3 '14 at 17:21
-2
$\begingroup$

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.

$\endgroup$
  • 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$ – Peng Zhang Apr 12 '14 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$ – Super8 Apr 12 '14 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$ – Peng Zhang Apr 12 '14 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$ – Super8 Apr 12 '14 at 3:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.