On the Alon-Tarsi number of semi-strong product of graphs

作者：Niu, Lin; Li, Xiangwen^*

来源：JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47(1): 1.

DOI：10.1007/s10878-023-01099-2

• Alon-Tarsi number
• List coloring
• Graph coloring
• Semi-strong product
• Combinatorial nullstellensatz

The Alon-Tarsi number was defined by Jensen and Toft (Graph coloring problems, Wiley, New York, 1995). The Alon-Tarsi number AT(G) of a graph G is the smallest integer k such that G has an orientation D with maximum outdegree k-1 and the number of even circulation is not equal to that of odd circulations in D. It is known that chi(G)<=chi l(G)<= AT(G) for any graph G, where chi(G) and chi(1)( G) are the chromatic number and the list chromatic number of G. Denote by H-1 square H-2 and H-1 (sic) H-2 the Cartesian product and the semi-strong product of two graphs H-1 and H-2, respectively. Kaul and Mudrock (Electron J Combin 26(1):P1.3, 2019) proved that AT(C2k+ 1 square P-n) = 3. Li, Shao, Petrov and Gordeev (Eur J Combin 103697, 2023) proved that AT(C-n square C-2k) = 3 and AT(C2m+ 1 square C2n+1) = 4. Petrov and Gordeev (Mosc. J. Comb. Number Theory 10(4):271-279, 2022) proved that AT(Kn square C-2k) = n. Note that the semi-strong product is noncommutative. In this paper, we determine AT( P-m (sic) P-n), AT(C-m (sic) C-2n), AT(C-m (sic) P-n) and AT( P-m (sic) C-n). We also prove that 5 <= AT(C-m (sic) C2n+1) <= 6.