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

zbMATH Open1409.05110arXiv1803.07455MaRDI QIDQ668046FDOQ668046

J. A. Mudrock, Hemanshu Kaul

Publication date: 5 March 2019

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

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.

Full work available at URL: https://arxiv.org/abs/1803.07455

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)

Cites Work

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

Cited In (6)

• The Alon-Tarsi number of a toroidal grid
• Flexible list colorings: maximizing the number of requests satisfied
• Combinatorial Nullstellensatz and DP-coloring of graphs
• On the Alon-Tarsi number of semi-strong product of graphs
• Acyclic choosability of graphs with bounded degree
• The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda

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)