3-choosability of triangle-free planar graphs with constraints on 4-cycles

Abstract

We prove that if a triangle-free planar graph is not 3-choosable, then it contains a 4-cycle that intersects another 4- or 5-cycle in exactly one edge. This strengthens Thomassen's result [C.

Thomassen, J. Combin.

Theory Ser. B, 64 (1995), pp. 101-107] that every planar graph of girth at least 5 is 3-choosable.

Keywords

• planar graph
• triangle-free graph
• coloring
• list coloring
• choosability