Equitable Vertex Arboricity Conjecture for bounded-degree graphs

About 7 years old · traced to

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-k′k'-coloring for every integer k′≥kk'\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.

References

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.