Wu–Zhang–Li equitable vertex arboricity conjecture

Let GG be a graph. A vertex kk-arborable graph has a (not necessarily proper) kk-coloring whose color classes induce acyclic subgraphs; it is equitably vertex kk-arborable if the sizes of the color classes differ by at most one. Let Δ(G)\Delta(G) denote the maximum degree.

Wu–Zhang–Li conjecture. Graph GG is equitably vertex kk-arborable whenever

kΔ(G)+12.k\geq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil.

The conjecture is a well-known equitable analogue of vertex arboricity and has received attention in the literature; the supplied text does not state a resolution.

Sources & referencesView supporting material

Primary source

Hemanshu Kaul, Jeffrey A. Mudrock and Michael J. Pelsmajer, “On Equitable List Arboricity of Graphs”, arXiv:2008.08926 (2021).

Additional references

3 papers in this index state this conjecture (2019–2020). The statement above is taken from the most recent of them; the others are arXiv:1908.05075, arXiv:1903.08337.

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.