The sub-nine acyclic list-colouring conjecture for locally planar graphs

Let GG be a graph embedded in a surface Σ\Sigma, and let g(Σ)g(\Sigma) denote the genus of Σ\Sigma. A graph is ρ\rho-locally planar if the relevant local planarity condition holds with parameter ρ\rho. An acyclic kk-list-colouring is a list-colouring from lists of size kk in which every cycle receives at least three colours. Sub-nine acyclic list-colouring conjecture. There exists an integer k<9k<9 and a value ρ=ρ(g(Σ))\rho=\rho(g(\Sigma)) such that every ρ\rho-locally planar graph embedded in Σ\Sigma is acyclically kk-list-colourable.

The paper proves the corresponding bound with 99 colours and notes that the list size is probably not optimal. It suggests that k=8k=8 may be attainable, while k=7k=7 is also considered possible; the optimal value remains unclear.

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.