Document Type

Article

Publication Title

Journal of Combinatorial Theory

Publication Date

2026

Keywords

correspondence colouring, planar graph, locally planar, embedded graph, hyperbolic family

Abstract

We show that there exists a constant c>0 such that if G is a planar graph with a 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.

Funding Source

This article was published open access thanks to a transformative agreement between Milner Library and Elsevier.

Comments

First published in Journal of Combinatorial Theory (2026): https://doi.org/10.1016/j.jctb.2026.09.003

DOI

10.1016/j.jctb.2026.09.003

Download

Included in

Mathematics Commons

Share

COinS