Zhang's equitable list arboricity conjecture

About 8 years old · traced to

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.

References

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.