PreprintarXiv licencearXiv
The Alon-Tarsi number of 4-regular circulant graphs
Abstract
This paper studies the Alon-Tarsi number of connected $4$-regular circulant graphs Cn(s,t), where 1≤ s<t<n/2. We prove that if n=ℓ pr, where p is an odd prime, r≥ 1, and t≡± spmodℓ, then AT(Cn(s,t))=3 if ℓ is even, or if ℓ≥ 3 is odd and pnmid 2ℓ−2. We also prove that AT(C6m(2,3))=3 for m≥ 2, and AT(Cn(1,3))=3 for n≥ 8.
Related
- Existence of regular sets in circulant quartic graphs: a complete characterization
- Sharp asymptotics for the Lovász number of random circulant graphs
- A sharp upper bound on the number of spanning forests of regular graphs
- Logarithmic basis number of graphs and regular matroids
- The maximum number of triangles in regular graphs
BibTeX
@misc{xu2026alontarsi,
title = {{The Alon-Tarsi number of 4-regular circulant graphs}},
author = {Xinbo Xu and Xuding Zhu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41820},
eprint = {2610.41820},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41820},
}
RIS
TY - UNPB
TI - The Alon-Tarsi number of 4-regular circulant graphs
AU - Xinbo Xu
AU - Xuding Zhu
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41820
UR - https://arxiv.org/abs/2610.41820
AB - This paper studies the Alon-Tarsi number of connected $4$-regular circulant graphs C_n(s,t), where 1≤ s<t<n/2. We prove that if n=ℓ p^r, where p is an odd prime, r≥ 1, and t≡± spmodℓ, then AT(C_n(s,t))=3 if ℓ is even, or if ℓ≥ 3 is odd and pnmid 2^ℓ−2. We also prove that AT(C_6m(2,3))=3 for m≥ 2, and AT(C_n(1,3))=3 for n≥ 8.
ER -