The Alon-Tarsi Number of A Toroidal Grid

2019/12/28 by Zhiguo Li, Li, Zhiguo, Zeling Shao +5
Computer Science · #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1912.12466

openalex publication_date 2019/12/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Alon-Tarsi number AT(G) of a graph G is the smallest k for which there is an orientation D of G with max indegree k-1 such that the number of even and odd circulations contained in D are different. In this paper, we show that the Alon--Tarsi number of toroidal grids T_m,n=C_m\Box C_n equals 4 when m,n are both odd and 3 otherwise.

Related

• The Alon-Tarsi number of Halin graphs
• The Alon-Tarsi Number of Cartesian product and Corona product of Hypercube Graph and Special Graphs
• The Alon-Tarsi number of planar graphs -- a simple proof
• The Alon-Tarsi number of K₅-minor-free graphs
• The Alon-Tarsi number of a planar graph minus a matching