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!

  • $\begingroup$ What is the example that shows that this bound would be sharp? $\endgroup$ – domotorp Sep 28 '17 at 9:01
  • 1
    $\begingroup$ 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$. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ You're welcome, I hope this was useful. $\endgroup$ – Louis Esperet Oct 10 '17 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.