Planar equitable vertex arboricity conjecture

About 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

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.