Planar equitable vertex arboricity conjecture
Planar equitable vertex arboricity conjecture
Let be a planar graph, and let denote the least integer such that has an equitable tree--coloring for every integer , where an equitable tree--coloring has forest color classes whose sizes differ pairwise by at most .
Planar equitable vertex arboricity conjecture. There exists a constant such that every planar graph is equitably tree--colorable for every integer ; equivalently,
This conjecture was proposed by Wu, Zhang and Li and was later confirmed by Esperet, Lemoine and Maffray, who proved the stronger explicit bound for every planar graph. Thus the conjecture is solved.
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).
Additional references
2 papers in this index state this conjecture (2016–2019). The statement above is taken from the most recent of them; the others are arXiv:1608.05352.
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.