Zhang's equitable list arboricity conjecture

Let GG be a graph, let LL be a kk-assignment for GG, and call GG equitably kk-list arborable if there is an arborable LL-coloring in which every color class has size at most V(G)/k\lceil |V(G)|/k\rceil for every such LL. Write Δ(G)\Delta(G) for the maximum degree of GG.

Zhang's conjecture. Any graph GG is equitably kk-list arborable for each kk satisfying

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

The conjecture is a list analogue of the Equitable Vertex Arboricity Conjecture. It has been verified for 2-degenerate graphs, 3-degenerate claw-free graphs with maximum degree at least 44, planar graphs with maximum degree at least 88, and grids of dimensions 22, 33, and 44, but remains open in general.

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

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

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.