On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs (Q668046)

Summary: We study the list chromatic number of Cartesian products of graphs through the Alon-Tarsi number as defined by \textit{T. R. Jensen} and \textit{B. Toft} in their seminal book on graph coloring problems [Graph coloring problems. New York, NY: John Wiley \& Sons (1995; Zbl 0855.05054)]. The \textit{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) \leq \chi_\ell(G) \leq \chi_p(G) \leq 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) \leq \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.