ÀÏÍõÂÛ̳

Title: Local Weak Degeneracy for Planar Graphs

 

Abstract: In 1994, Thomassen proved that every planar graph is 5-list-colourable, resolving a conjecture initially posed by Vizing and, independently, Erd\H{os}, Rubin, and Taylor in the 1970s. Later, Thomassen proved that every planar graph with no 3- or 4-cycle is 3-list-colourable. In 2022, Postle and I proved a list-colouring theorem for planar graphs wherein list sizes are localized, and depend on the shortest cycle in which each vertex is contained.  Our theorem unites and strengthens both listed theorems of Thomassen. Recently, Davies and I improved upon this further by proving an analogous theorem for correspondence colouring, a generalization of list colouring. In fact, our theorem holds even in the much more restrictive setting of weak degeneracy. I will introduce list colouring, correspondence colouring, and weak degeneracy, and give a high level overview of the main ideas behind our proof. Joint work with Ewan Davies.