Acyclic list colouring locally planar graphs
A (vertex) colouring of graph is acyclic if it contains no bicoloured cycle. In 1979, Borodin proved that planar graphs are acyclically 5-colourable. In 2010, Kawarabayashi and Mohar proved that locally planar graphs are acyclically 7-colourable. In 2002, Borodin, Fon-Der-Flaass, Kostochka, Raspaud, and Sopena proved that planar graphs are acyclically 7-list-colourable. We prove that locally planar graphs are acyclically 9-list-colourable—no bound for acyclic list colouring locally planar graphs for any fixed number of colours was previously known.
Authors
- Evelyne Smith‐Roberge (ORCID: https://orcid.org/0009-0000-0027-7657)
- Luke Postle (ORCID: https://orcid.org/0000-0002-5023-269X)
- Massimo Vicenzo
Institutions
- University of Waterloo (CA)
- Illinois State University (US)
Publication Details
- Journal
- Journal of Combinatorial Theory Series B
- Published
- 2026-09-30
- DOI
- https://doi.org/10.1016/j.jctb.2026.09.004
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Natural Sciences and Engineering Research Council of Canada