Bounded equitable vertex arborable threshold for planar graphs

Let GG be a simple finite planar graph, and let va(G)va^{\equiv}(G) denote its equitable vertex arborable threshold: the minimum integer kk such that GG admits an equitable tree-kk'-coloring for every integer kkk'\geq k. A tree-kk-coloring is a coloring of V(G)V(G) with colors 1,2,,k1,2,\dots,k such that each color class induces a forest, and the coloring is equitable when any two color-class sizes differ by at most one. Bounded planar equitable vertex arborable threshold conjecture. There is a constant CC such that

va(G)Cva^{\equiv}(G)\leq C

for every planar graph GG. This asks whether the equitable vertex arborable threshold is bounded independently of the size and maximum degree of planar graphs; the source provides no evidence of resolution.

Sources & referencesView supporting material

Primary source

Xin Zhang and Bei Niu, “Equitable partition of graphs into induced linear forests”, arXiv:1908.05075 (2019).

Additional references

2 papers in this index state this conjecture (2014–2019). The statement above is taken from the most recent of them; the others are arXiv:1403.2810.

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.