Strong equitable vertex arboricity bounded by maximum degree

About 12 years old · traced to

Let GG be a graph, let Δ(G)\Delta(G) denote its maximum degree, and let aeq∗(G)a^*_{eq}(G) be the smallest integer tt such that GG has an equitable t′t'-tree-coloring for every t′≥tt'\geq t, where an equitable kk-tree-coloring is a partition of V(G)V(G) into kk parts whose sizes differ by at most one and each part induces a forest. Strong equitable vertex arboricity conjecture.

aeq∗(G)≤⌈Δ(G)+12⌉a^*_{eq}(G)\leq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil

This conjecture proposes a maximum-degree bound for the strong equitable vertex arboricity of every graph. Its resolution is not specified in the source.

References

Primary source

Xin Zhang, “Equitable vertex arboricity of planar graphs”, arXiv:1403.2810 (2014).

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.