Acyclic list colouring of planar graphs.

High ★★★ Graph Theory » Coloring » Vertex coloring

Authors: Borodin, Oleg V., Fon-Der-Flasss, D. G., Kostochka, Alexandr V., Raspaud, André, Sopena, Eric— posted by fhavet on 2013-03-07

Status partial high confidence

The conjecture that every planar graph is acyclically 5-choosable remains open. Before the OPG posting, Borodin and Ivanova (2011, Siberian Math. J.) had already established the conjecture for planar graphs without 4-cycles; post-2013 work has continued to prove acyclic choosability (with 4 or 5 colors) for increasingly refined restricted classes of planar graphs. A 2024 arXiv preprint establishes the first fixed bound for acyclic list colouring of locally planar graphs (embedded in any surface), showing acyclic 9-list-colourability, but does not resolve the planar 5-choosability conjecture.

Cited literature (2)

partial Acyclic 4-choosability of planar graphs without 4-cycles (2020)

Yingcai Sun, Min Chen · Czechoslovak Mathematical Journal · doi:10.21136/CMJ.2019.0197-18

Every planar graph with neither 4-cycles nor intersecting $i$-cycles for each $i\in\{3,5\}$ is acyclically 4-choosable, advancing the Montassier–Raspaud–Wang conjecture for restricted subclasses.
partial Acyclic List Colouring Locally Planar Graphs (2024)

Luke Postle, Evelyne Smith-Roberge, Massimo Vicenzo · arXiv preprint · arXiv:2412.09410

Locally planar graphs embedded in any fixed surface are acyclically 9-list-colourable (the first finite bound for acyclic list colouring beyond the plane), extending the planar 7-list-colourability result of Borodin et al. (2002) to more general surfaces.

Reviewer notes. The Borodin–Ivanova result proving acyclic 5-choosability for planar graphs without 4-cycles (Siberian Math. J. 52, 2011) predates the OPG posting (2013-03-07) and is therefore not in since_posted. Several post-2013 papers on acyclic 4-choosability for restricted planar graph classes (e.g., ScienceDirect 2021 paper on no cycles of length 4, 7, 9) could not be verified via WebFetch due to HTTP 403 responses. The 2024 Postle–Smith-Roberge–Vicenzo preprint concerns locally planar graphs on general surfaces; it does not resolve or improve the bound of 7 for plain planar graph acyclic list coloring. No evidence was found that the full conjecture (all planar graphs are acyclically 5-choosable) has been resolved.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (web search enabled) · 191s.

Conjecture. Every planar graph is acyclically 5-choosable.

Discussion

This conjecture would imply to celebrated 5-colour theorems: one due toBorodin [B] stating that every planar graph is acyclically 5-colourable, and one due to Thomassen [T] stating that every plaanar graph is 5-choosable. This two theorems are best possible, because there are planar graphs which are not acyclically 4-colourable and others which are not 4-choosable. Borodin et al. [BFKRS] showed that every planar graph is acyclically 7-choosable.

Bibliography

[B] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math. 25 (1979) 211-236.
★ [BFKRS] O.V. Borodin, D.G. Fon-Der Flaass, A.V. Kostochka, A. Raspaud, and E. Sopena, Acyclic list 7-coloring of planar graphs, J. of Graph Theory 40-2 (2002) 83-90.
[T] C. Thomassen. Every planar graph is 5-choosable. J. Combin. Theory Ser. B, 62(1994), no. 1, 180–181.
[V] M. Voigt. List colourings of planar graphs. Discrete Math., 120(1993):no. 1-3, 215–219.