Equitable Vertex Arboricity Conjecture for bounded-degree graphs

Let GG be a graph with maximum degree at most Δ\Delta. An equitable tree-kk-coloring of GG assigns each vertex a color in {1,2,,k}\{1,2,\ldots,k\} so that every color class induces a forest and the sizes of any two color classes differ by at most 11. The equitable vertex arborable threshold vaeq(G)va_{eq}^*(G) is the least integer kk such that GG has an equitable tree-kk'-coloring for every integer kkk'\geq k.

Equitable Vertex Arboricity Conjecture. Every graph with maximum degree at most Δ\Delta is equitably tree-kk-colorable for every integer k(Δ+1)/2k\geq (\Delta+1)/2; equivalently,

vaeq(G)(Δ+1)/2.va_{eq}^*(G)\leq \lceil(\Delta+1)/2\rceil.

Wu, Zhang and Li proposed this conjecture. It is known for all 5-degenerate graphs, and hence for graphs with maximum degree at most 55, but remains open in general.

Sources & referencesView supporting material

Primary source

Xin Zhang, Bei Niu, Yan Li and Bi Li, “Equitable vertex arboricity conjecture holds for graphs with low degeneracy”, arXiv:1908.05066 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.