Planar equitable vertex arboricity conjecture

Let GG be a planar graph, and let vaeq(G)va_{eq}^*(G) denote the least integer kk such that GG has an equitable tree-kk'-coloring for every integer kkk'\geq k, where an equitable tree-kk'-coloring has forest color classes whose sizes differ pairwise by at most 11.

Planar equitable vertex arboricity conjecture. There exists a constant kk such that every planar graph is equitably tree-kk'-colorable for every integer kkk'\geq k; equivalently,

vaeq(G)k.va_{eq}^*(G)\leq k.

This conjecture was proposed by Wu, Zhang and Li and was later confirmed by Esperet, Lemoine and Maffray, who proved the stronger explicit bound vaeq(G)4va_{eq}^*(G)\leq 4 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

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.