Planar graph

Statistics

Combinatorics

Discrete mathematics

Computer graphics (images)

Graph

Planar

Matching (statistics)

Mathematics

Computer science

Journal of Combinatorial Theory Series B

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 (2010) [5], who proved that every planar graph is 1-defective 4-choosable.

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