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?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
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.