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

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$$ k - 1 and the number of even circulation is not equal to that of odd circulations in D. It is known that $$\chi (G)\le \chi _l(G)\le AT(G)$$ χ ( G ) ≤ χ l ( G ) ≤ A T ( G ) for any graph G, where $$\chi (G)$$ χ ( G ) and $$\chi _l(G)$$ χ l ( G ) are the chromatic number and the list chromatic number of G. Denote by $$H_1 \square H_2$$ H 1 □ H 2 and $$H_1\bowtie H_2$$ H 1 ⋈ H 2 the Cartesian product and the semi-strong product of two graphs $$H_1$$ H 1 and $$H_2$$ H 2 , respectively. Kaul and Mudrock (Electron J Combin 26(1):P1.3, 2019) proved that $$AT(C_{2k+1}\square P_n)=3$$ A T ( C 2 k + 1 □ P n ) = 3 . Li, Shao, Petrov and Gordeev (Eur J Combin 103697, 2023) proved that $$AT(C_n\square C_{2k})=3$$ A T ( C n □ C 2 k ) = 3 and $$AT(C_{2m+1}\square C_{2n+1})=4$$ A T ( C 2 m + 1 □ C 2 n + 1 ) = 4 . Petrov and Gordeev (Mosc. J. Comb. Number Theory 10(4):271–279, 2022) proved that $$AT(K_n\square C_{2k})=n$$ A T ( K n □ C 2 k ) = n . Note that the semi-strong product is noncommutative. In this paper, we determine $$AT(P_m \bowtie P_n)$$ A T ( P m ⋈ P n ) , $$AT(C_m \bowtie C_{2n})$$ A T ( C m ⋈ C 2 n ) , $$AT(C_m \bowtie P_n)$$ A T ( C m ⋈ P n ) and $$AT(P_m \bowtie C_{n})$$ A T ( P m ⋈ C n ) . We also prove that $$5\le AT(C_m \bowtie C_{2n+1})\le 6$$ 5 ≤ A T ( C m ⋈ C 2 n + 1 ) ≤ 6 .