pith. sign in

arxiv: 1811.12012 · v1 · pith:U4H6HPEInew · submitted 2018-11-29 · 🧮 math.CO

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

classification 🧮 math.CO
keywords planargraphalon-tarsichoosabledefectiveeverymatchingnumber
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.