# vertex arboricity and chromatic number of triangle-free graphs

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!

• What is the example that shows that this bound would be sharp? – domotorp Sep 28 '17 at 9:01
• If I'm not mistaken, a simple example in which the bound is sharp would be the Mycielskian $\mu(C_5)$ of the $5$-cycle $C_5$, as $va(\mu(C_5))=2$ and $\chi(\mu(C_5))=4$. – Yusuf Civan Sep 28 '17 at 10:18

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.