The Alon-Tarsi number of planar graphs without some forbidden configurations

School of Mathematics and Statistics, Weifang University, Weifang 261061, P.R. China

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 23 April 2025
Accepted: 25 January 2026

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.