The Alon-Tarsi number of a planar graph minus a matching

Abstract

This paper proves that every planar graph $G$ contains a matching $M$ such that the Alon-Tarsi number of $G-M$ is at most $4$. As a consequence, $G-M$ is $4$-paintable, and hence $G$ itself is $1$-defective $4$-paintable. This improves a result of Cushing and Kierstead [Planar Graphs are 1-relaxed, 4-choosable, {\em European Journal of Combinatorics} 31(2010),1385-1397], who proved that every planar graph is $1$-defective $4$-choosable.

11 pages

References in corpus (1)

• Defective 3-Paintability of Planar Graphs

Cited by in corpus (5)

• The Alon-Tarsi number of subgraphs of a planar graph
• The Alon-Tarsi number of Halin graphs
• Laurent polynomials of planar graphs
• The Alon-Tarsi number of planar graphs without cycles of lengths $4$ and $l$
• List colouring triangle free planar graphs