Equitable Vertex Arboricity Conjecture for bounded-degree graphs
Equitable Vertex Arboricity Conjecture for bounded-degree graphs
Let be a graph with maximum degree at most . An equitable tree--coloring of assigns each vertex a color in so that every color class induces a forest and the sizes of any two color classes differ by at most . The equitable vertex arborable threshold is the least integer such that has an equitable tree--coloring for every integer .
Equitable Vertex Arboricity Conjecture. Every graph with maximum degree at most is equitably tree--colorable for every integer ; equivalently,
Wu, Zhang and Li proposed this conjecture. It is known for all 5-degenerate graphs, and hence for graphs with maximum degree at most , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.