← All problems

Planar equitable vertex arboricity conjecture

10 years old · traced to

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-k′k'-coloring for every integer k′≥kk'\geq k, where an equitable tree-k′k'-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-k′k'-colorable for every integer k′≥kk'\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.

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.

Status

  • Solved: Louis Esperet, Frédéric Lemoine, and Frédéric Maffray. Equitable tree-coloring of planar graphs (arXiv, 2014) https://arxiv.org/abs/1403.2810

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.