The Alon-Tarsi number of $K_{3,3}$-minor-free graphs
Abstract
The well known Wagner's theorem states that a graph is a planar graph if and only if it is $K_5$-minor-free and $K_{3,3}$-minor-free. Denote by $AT(G)$ the Alon-Tarsi number of a graph $G$. We show that for any $K_{3,3}$-minor-free graph $G$, $AT(G)\le 5$, there exists a matching $M$ and a forest $F$ such that $AT(G-M)\le 4$ and $AT(G-E(F))\le 3$, extending the result on the Alon-Tarsi number of $K_5$-minor-free graphs due to Abe, Kim and Ozeki.
Fields of Study & Subjects
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Czechoslovak Mathematical Journal
- Volume
- 76
- Issue
- 3
- Pages
- 737–745
- Publication date
- 7 August 2026
- Language
- EN