$4$-choosability of planar graphs with $4$-cycles far apart via the Combinatorial Nullstellensatz

Abstract

By a well-known theorem of Thomassen and a planar graph depicted by Voigt, we know that every planar graph is $5$-choosable, and the bound is tight. In 1999, Lam, Xu and Liu reduced $5$ to $4$ on $C_4$-free planar graphs. In the paper, by applying the famous Combinatorial Nullstellensatz, we design an effective algorithm to deal with list coloring problems. At the same time, we prove that a planar graph $G$ is $4$-choosable if any two $4$-cycles having distance at least $5$ in $G$, which extends the result of Lam et al.