On the Alon-Tarsi Number and Chromatic-choosability of Cartesian Products of Graphs

Abstract

We study the list chromatic number of Cartesian products of graphs through the Alon-Tarsi number as defined by Jensen and Toft (1995) in their seminal book on graph coloring problems. The Alon-Tarsi number of $G$, $AT(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. It is known that $\chi (G)\le {\chi }_{\ell }(G)\le {\chi }_p(G)\le AT(G)$, where $\chi (G)$ is the chromatic number, ${\chi }_{\ell }(G)$ is the list chromatic number, and ${\chi }_p(G)$ is the paint number of $G$. In this paper we find families of graphs $G$ and $H$ such that $\chi (G\square H)=AT(G\square H)$, reducing this sequence of inequalities to equality. We show that the Alon-Tarsi number of the Cartesian product of an odd cycle and a path is always equal to 3. This result is then extended to show that if $G$ is an odd cycle or a complete graph and $H$ is a graph on at least two vertices containing the Hamilton path $w_1,w_2,\dots ,w_n$ such that for each $i$, $w_i$ has a most $k$ neighbors among $w_1,w_2,\dots ,w_{i-1}$, then $AT(G\square H)\le \Delta (G)+k$ where $\Delta (G)$ is the maximum degree of $G$. We discuss other extensions for $G\square H$, where $G$ is such that $V(G)$ can be partitioned into odd cycles and complete graphs, and $H$ is a graph containing a Hamiltonian path. We apply these bounds to get chromatic-choosable Cartesian products, in fact we show that these families of graphs have $\chi (G)=AT(G)$, improving previously known bounds.

arXiv comment12 pages