2018/11/29 by Grytczuk, Jarosław, Zhu, Xuding
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1811.12012
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.