Planar equitable tree-3-coloring conjecture

At least 6 years old · documented by

Let GG be a planar graph. An equitable tree-33-coloring is a coloring of V(G)V(G) with three colors such that each color class induces a forest and any two color classes differ in size by at most 11. Write vaeq∗(G)va_{eq}^*(G) for the least integer kk such that GG has an equitable tree-k′k'-coloring for every integer k′≥kk'\geq k.

Planar equitable tree-3-coloring conjecture. Every planar graph is equitably tree-33-colorable; equivalently,

vaeq∗(G)≤3.va_{eq}^*(G)\leq 3.

The preceding bound vaeq∗(G)≤4va_{eq}^*(G)\leq 4 for planar graphs leaves only this sharper case. The source presents it as a natural conjecture, and no resolution is supplied there.

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).

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.