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

Lin Niu and Xiangwen Li ()
Additional contact information
Lin Niu: Central China Normal University
Xiangwen Li: Central China Normal University

Journal of Combinatorial Optimization, 2024, vol. 47, issue 1, No 1, 19 pages

Abstract: Abstract 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 .

Keywords: Alon–Tarsi number; List coloring; Graph coloring; Semi-strong product; Combinatorial nullstellensatz (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01099-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:1:d:10.1007_s10878-023-01099-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01099-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().