List-coloring is a natural variant of graph coloring, where every vertex v of a graph G starts with its own list L(v) of colors, and the goal is to find a proper coloring of G in which each vertex v receives a color from its list L(v). We call this coloring an L-coloring. Saying that a graph G has an L-coloring when all lists L(v) are equal to {1,…,k} is equivalent to saying that G is k-colorable. One might expect that having fairly different lists makes it easier to color the graph, but it turns out not to be the case, as it is known that the vertices of the complete bipartite graph Kn,n can be assigned lists L(v) of Ω(logn) colors, such that Kn,n has no L-coloring.
In view of the Four color theorem, a natural problem is to find the smallest integer k, such that for all lists L(v) of size at least k in a planar graph G, the graph G has an L-coloring. It was proved in 1993 by Voigt that k≥5, and shortly after that Thomassen proved that when all lists have size at least 5, all planar graphs have an L-coloring, so k=5. The proof of Thomassen is a very nice and short inductive argument, where the lists of the vertices of the outerface are restricted (to have size 1 or 3). Thomassen later showed using a similar technique (but a more involved proof) that if all vertices of a planar graph G of girth at least 5 (i.e. without cycles of length 3 or 4) have a list of size 3, then G has an L-coloring.
The main result of the present paper is a common strengthening of the two classical theorems of Thomassen mentioned above. Namely, if each vertex of a planar graph G has a list of colors of size at least 3, and at least 4 if it lies in a 4-cycle, and at least 5 if it lies in a triangle, then G has an L-coloring.
While “local” results are fairly common in the area of list-coloring (starting with results when each vertex has a list of colors of size equal to its degree for instance), this type of local result is new and unexpected.