# Hardness of approximating chromatic number of triangle-free graphs

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?

• 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. – Vivek Bagaria May 3 '14 at 17:21

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.
• 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. – Peng Zhang Apr 12 '14 at 3:21
• 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. – Super8 Apr 12 '14 at 3:31
• 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. – Peng Zhang Apr 12 '14 at 3:39
• 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. – Super8 Apr 12 '14 at 3:48