The Alon-Tarsi number of planar graphs without some forbidden configurations
Abstract
The Alon-Tarsi number of a graph G , denoted AT ( G ), defined as the smallest integer k admitting an Alon-Tarsi orientation with maximum out-degree at most k −1, satisfies the fundamental inequalities χ l ( G ) ≤ AT ( G ) ≤ d ( G ) + 1, where χ l ( G ) and d ( G ) denote the list chromatic number and degeneracy, respectively. Notably, for planar graphs without k -cycles where k ∈ {5,6}, the 3-degeneracy implies AT ( G ) ≤ 4, and our main result extends this by proving AT ( G ) ≤ 4 for planar graphs without 4-cycles adjacent to 3-cycles, thereby improving previous results from Lam et al. [ J. Comb. Theory. Ser. B 76 (1999) 117–126] and Cheng et al. [ Discrete Math. 339 (2016) 3052–3057]. We also show that this result is sharp.
Fields of Study & Subjects
Advanced Graph Theory Research
Graph Labeling and Dimension Problems
Limits and Structures in Graph Theory
Publication details
- Journal / source
- RAIRO - Operations Research
- Volume
- 60
- Issue
- 2
- Pages
- 615–624
- Publication date
- 30 January 2026
- Language
- EN