Maximum-degree bound for equitable vertex arboricity

Let GG be a graph, let Δ(G)\Delta(G) be its maximum degree, and let va,(G)va^{\equiv}_{\infty,\infty}(G) denote the strong equitable (,)(\infty,\infty)-vertex-arboricity. Maximum-degree equitable vertex arboricity conjecture. For every graph GG,

va,(G)Δ(G)+12.va^{\equiv}_{\infty,\infty}(G)\leq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil.

The paper notes that the planar conjecture does not extend to general graphs, since some complete bipartite graphs have strong equitable vertex arboricity of order Ω(G1/2)\Omega(|G|^{1/2}). This degree bound is proposed as a possible general-graph replacement and remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Jian-Liang Wu, Xin Zhang and Hailun Li, “Equitable vertex arboricity of graphs”, arXiv:1211.4193 (2012).

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.