<p>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.</p>

CC BY-SA 3.0
2014-04-12T03:21:36.323Z
It is NP-Complete to find $\chi(G)$ for triangle-free graphs. Mentioned here, http://konrad127123.s3-website-eu-west-1.amazonaws.com/Triangle-free.pdf I think your algorithm fails for $C_4$, a cycle of four vertices.
Peng Zhang
CC BY-SA 3.0
2014-04-12T03:31:14.380Z
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
CC BY-SA 3.0
2014-04-12T03:39:27.920Z
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
CC BY-SA 3.0
2014-04-12T03:48:41.443Z
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
CC BY-SA 3.0
2014-04-12T03:09:46.593Z
2014-04-12T03:09:46.593Z
Super8
<p>The <a href="http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity" rel="noreferrer">chromatic number</a> of graph, $\chi( G)$ is hard to approximate for general graphs. </p>

<p>Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?</p>

CC BY-SA 3.0
2014-05-03T17:21:50.940Z
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
<graph-theory><approximation-algorithms><approximation-hardness>
Hardness of approximating chromatic number of triangle-free graphs
Peng Zhang
# Hardness of approximating chromatic number of triangle-free graphs

(Asked by: username_0 on 2014-04-12)

The [chromatic number](http://en.wikipedia.org/wiki/Graph_coloring#Computational_complexity) of graph, $\chi( G)$ is hard to approximate for general graphs.

Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?

**Tags:** graph-theory, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-04-12. Score: -2

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.

> **Comments:**
> **username_0**: It is NP-Complete to find $\chi(G)$ for triangle-free graphs. Mentioned here, http://konrad127123.s3-website-eu-west-1.amazonaws.com/Triangle-free.pdf I think your algorithm fails for $C_4$, a cycle of four vertices.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: 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.  

---

