vertex arboricity and chromatic number of triangle-free graphs

Question

For a (finite and simple) graph $G=(V,E)$, the vertex arboricity, $va(G)$ of $G$ is defined to be the least integer $d$ such that the vertex set of $G$ has a partition $V=V_1\cup V_2\cup \ldots \cup V_d$ for which the induced subgraph $G[V_i]$ is a forest for each $i=1,2,\ldots,d$.

Question: Is it true that $\chi(G)\leq va(G)+2$ for any triangle-free graph $G$?

ps. The condition "triangle-freeness" of $G$ is necessary for the stated bound, since otherwise the complete graph $K_n$ for some $n\geq 6$ provides a counterexample!

Answer 1

No.

A graph is $d$-degenerate if every subgraph contains a vertex of degree at most $d$. Alon Krivelevich and Sudakov showed that there are $d$-degenerate triangle-free graphs with chromatic number $d+1$. http://www.tau.ac.il/~nogaa/PDFS/logf4.pdf

Now, if a graph is $d$-degenerate, it is not difficult to see that its vertex-arboricity is at most $d/2+1$. To prove this, take a vertex $v$ of degree at most $d$, remove it, color your graph by induction, and then pick a color for $v$ that appears at most once in its neighborhood (by the pigeonhole principle such a color exists). In the resulting coloring every color-class is a forest, as desired.

This shows that the graphs of Alon Krivelevich and Sudakov have $\chi=d+1$ and $va\le d/2+1$, so there might be a factor 2 between the two parameters, even for triangle-free graphs.