2023/03/29 by Luke Postle, Postle, Luke, Evelyne Smith‐Roberge +1
Computer Science · #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2303.16997
openalex publication_date 2023/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We generalize a framework of list colouring results to correspondence colouring. Correspondence colouring is a generalization of list colouring wherein we localize the meaning of the colours available to each vertex. As pointed out by Dvořák and Postle, both of Thomassen's theorems on the 5-choosability of planar graphs and 3-choosability of planar graphs of girth at least five carry over to the correspondence colouring setting. In this paper, we show that the family of graphs that are critical for 5-correspondence colouring as well as the family of graphs of girth at least five that are critical for 3-correspondence colouring form hyperbolic families. Analogous results for list colouring were shown by Postle and Thomas and by Dvořák and Kawarabayashi, respectively. Using results on hyperbolic families due to Postle and Thomas, we show further that this implies that locally planar graphs are 5-correspondence colourable; and, using results of Dvořák and Kawarabayashi, that there exist linear-time algorithms for the decidability of 5-correspondence colouring for embedded graphs. We show analogous results for 3-correspondence colouring graphs of girth at least five.