Luke Postle

Exponentially many correspondence colourings of planar and locally planar graphs

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 $2^{c\cdot v(G)}$ distinct $(L,M)$-colourings. This confirms a conjecture of Langhede and Thomassen. More broadly, we introduce a genera...

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,...