English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the list chromatic number of Cartesian products of graphs throughthe Alon-Tarsi number as defined by Jensen and Toft (1995) in their seminalbook on graph coloring problems. The Alon-Tarsi number of $G$, $AT(G)$, is thesmallest $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) \leqAT(G)$, where $\chi(G)$ is the chromatic number, $\chi_\ell(G)$ is the listchromatic number, and $\chi_p(G)$ is the paint number of $G$. In this paper wefind families of graphs $G$ and $H$ such that $\chi(G \square H) = AT(G \squareH)$, reducing this sequence of inequalities to equality. We show that theAlon-Tarsi number of the Cartesian product of an odd cycle and a path is alwaysequal to 3. This result is then extended to show that if $G$ is an odd cycle ora complete graph and $H$ is a graph on at least two vertices containing theHamilton path $w_1, w_2, \ldots, w_n$ such that for each $i$, $w_i$ has a most$k$ neighbors among $w_1, w_2, \ldots, w_{i-1}$, then $AT(G \square H) \leq\Delta(G)+k$ where $\Delta(G)$ is the maximum degree of $G$. We discuss otherextensions for $G \square H$, where $G$ is such that $V(G)$ can be partitionedinto odd cycles and complete graphs, and $H$ is a graph containing aHamiltonian path. We apply these bounds to get chromatic-choosable Cartesianproducts, in fact we show that these families of graphs have $\chi(G) = AT(G)$,improving previously known bounds.

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