The Alon-Tarsi number of K₅-minor-free graphs

2019/11/11 by Abe, Toshiki, Kim, Seog-Jin, Ozeki, Kenta
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1911.04067

Abstract

In this paper, we show the following three theorems. Let G be a K₅-minor-free graph. Then Alon-Tarsi number of G is at most 5, there exists a matching M of G such that the Alon-Tarsi number of G-M is at most 4, and there exists a forest F such that the Alon-Tarsi number of G-E(F) is at most 3.

Related

• The Alon-Tarsi number of K_3,3-minor-free graphs
• The Alon-Tarsi number of planar graphs -- a simple proof
• The Alon-Tarsi number of planar graphs
• On the Alon-Tarsi Number of Some Line and Total graphs
• The Alon-Tarsi number of subgraphs of a planar graph