← All problems

Planar equitable tree-3-coloring conjecture

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