The logarithmic edge-width conjecture for acyclic list-colouring locally planar graphs

Let Σ\Sigma be a surface and let g(Σ)g(\Sigma) denote its genus. Fix an integer kk for which there is a value ρ0=ρ0(g(Σ))\rho_0=\rho_0(g(\Sigma)) such that every ρ0\rho_0-locally planar graph embedded in Σ\Sigma is acyclically kk-list-colourable. Logarithmic edge-width conjecture. There exists

ρ=O(logg(Σ))\rho=O(\log g(\Sigma))

such that every ρ\rho-locally planar graph embedded in Σ\Sigma is acyclically kk-list-colourable.

The paper's theorem improves the relevant edge-width dependence from exponential to linear in the genus, and this conjecture proposes a further logarithmic bound while preserving any fixed admissible list size kk. The supplied text does not indicate that the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Luke Postle, Evelyne Smith-Roberge and Massimo Vicenzo, “Acyclic List Colouring Locally Planar Graphs”, arXiv:2412.09410 (2024).

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.