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$ 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$ May 3, 2014 at 17:21

1 Answer 1


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$
    – Peng Zhang
    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$
    – Super8
    Apr 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$
    – Peng Zhang
    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$
    – Super8
    Apr 12, 2014 at 3:48

Your Answer

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

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