Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.

This is joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.