Separation conjecture for list arborability and equitable list arborability

About 8 years old · traced to

Let GG be a graph and let k∈Nk\in\mathbb{N}. A graph is kk-list arborable if every kk-uniform list assignment admits a list colouring whose colour classes induce acyclic graphs. Suppose also that GG has a kk-colouring in which every colour class has cardinality at most

⌈∣V(G)∣k⌉\left\lceil \frac{|V(G)|}{k}\right\rceil

and induces an acyclic graph.

Separation conjecture. There is a graph GG and k∈Nk\in\mathbb{N} satisfying both properties above, but GG is not equitably kk-list arborable.

The conjecture asserts that ordinary list arborability together with an equitable acyclic colouring need not imply equitable list arborability. The source proposes it as an open question without a resolution.

References

Primary source

Ewa Drgas-Burchardt, Janusz Dybizbański, Hanna Furmańczyk and Elzbieta Sidorowicz, “Equitable List Vertex Colourability and Arboricity of Grids”, arXiv:1809.08281 (2018).

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.