{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T18:57:12Z","timestamp":1773169032080,"version":"3.50.1"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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) \\leq \\chi_\\ell(G) \\leq \\chi_p(G) \\leq AT(G)$, where\u00a0 $\\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.\r\nWe 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, \\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$.\u00a0 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.<\/jats:p>","DOI":"10.37236\/7740","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T02:16:27Z","timestamp":1578622587000},"source":"Crossref","is-referenced-by-count":6,"title":["On the Alon-Tarsi Number and Chromatic-Choosability of Cartesian Products of Graphs"],"prefix":"10.37236","volume":"26","author":[{"given":"Hemanshu","family":"Kaul","sequence":"first","affiliation":[]},{"given":"Jeffrey A.","family":"Mudrock","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2019,1,11]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i1p3\/7762","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v26i1p3\/7762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T23:19:06Z","timestamp":1579216746000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v26i1p3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,11]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1,11]]}},"URL":"https:\/\/doi.org\/10.37236\/7740","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,11]]},"article-number":"P1.3"}}