The Department of Applied Mathematics is hosting an online seminar on Friday, April 4, from 3:30–4:30 p.m. Speake Evelyne Smith-Roberge will give a talk titled “Local Weak Degeneracy for Planar Graphs.” Email kaul@iit.edu to request a link.​

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