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

MaRDI QIDQ668046zbMATH OpenFDO

Authors Hemanshu Kaul, J. A. Mudrock

Publication date 5 March 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07455, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p3

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Graph operations (line graphs, products, etc.) (05C76)

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)leqch{i}_{e}ll(G)leqch{i}_p(G)leqAT(G)$, where $chi(G)$ is the chromatic number, $ch{i}_{e}ll(G)$ is the list chromatic number, and $ch{i}_p(G)$ is the paint number of $G$. In this paper we find families of graphs $G$ and $H$ such that $chi(GsquareH)=AT(GsquareH)$, 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,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(GsquareH)leqDelta(G)+k$ where $Delta(G)$ is the maximum degree of $G$. We discuss other extensions for $GsquareH$, 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.

Recommendations

• On two generalizations of the Alon-Tarsi polynomial method
• Alon-Tarsi numbers of direct products
• The Alon-Tarsi number of a toroidal grid
• The Alon-Tarsi number of planar graphs
• The Alon-Tarsi number of two kinds of planar graphs

Cites work

• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 889958 (Why is no real title available?)
• A proof of a conjecture of Ohba
• Asymptotically good list-colorings
• Choice number of 3-colorable elementary graphs
• Choosability of powers of circuits
• Colorings and orientations of graphs
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• List coloring of Cartesian products of graphs
• List edge and list total colourings of multigraphs
• Mr. Paint and Mrs. Correct
• On chromatic‐choosable graphs
• On two generalizations of the Alon-Tarsi polynomial method
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The Alon-Tarsi number of planar graphs
• The list chromatic index of a bipartite multigraph
• Three topics in online list coloring

Cited in

(13)

• The Alon-Tarsi number of a toroidal grid
• Flexible list colorings: maximizing the number of requests satisfied
• Combinatorial Nullstellensatz and DP-coloring of graphs
• Beyond degree choosability
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• The Alon-Tarsi number of two kinds of planar graphs
• On the Alon-Tarsi number of semi-strong product of graphs
• Acyclic choosability of graphs with bounded degree
• Alon-Tarsi numbers of direct products
• The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda
• Relation between the correspondence chromatic number and the Alon-Tarsi number
• An Alon-Tarsi style theorem for additive colorings

This page was built for publication: On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q668046)