2023/09/29 by Luke Postle, Postle, Luke, Evelyne Smith‐Roberge +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2309.17291
openalex publication_date 2023/09/29 · openalex created_date 2023/10/03 · openalex updated_date 2026/08/01
We show that there exists a constant c > 0 such that if G is a planar graph with 5-correspondence assignment (L,M), then G has at least 2c⋅ v(G) distinct (L,M)-colourings. This confirms a conjecture of Langhede and Thomassen. More broadly, we introduce a general method showing how hyperbolicity theorems for certain families of critical graphs can be used to derive lower bounds on the number of colourings of the associated class of planar graphs. Hence our main result follows from this method plus a technical theorem (that we proved in a previous paper) involving the hyperbolicity of graphs critical for 5-correspondence colouring. We further demonstrate our method in the case of counting 3-correspondence colourings of planar graphs of girth at least five. Finally, we use these theorems to show analogous results hold in the case of counting 5-correspondence colourings of locally planar graphs, and counting 3-correspondence colourings of locally planar graphs of girth at least five.