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

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

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

,

A T (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

c h i (G) l e q c h i_{e} l l (G) l e q c h i_{p} (G) l e q A T (G)

, where

c h i (G)

is the chromatic number,

c h i_{e} l l (G)

is the list chromatic number, and

c h i_{p} (G)

is the paint number of

G

. In this paper we find families of graphs

G

and

H

such that

c h i (G s q u a r e H) = A T (G s q u a r e 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}, l d o t s, w_{n}

such that for each

i

,

w_{i}

has a most

k

neighbors among

w_{1}, w_{2}, l d o t s, w_{i - 1}

, then

A T (G s q u a r e H) l e q D e l t a (G) + k

where

D e l t a (G)

is the maximum degree of

G

. We discuss other extensions for

G s q u a r e 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

c h i (G) = A T (G)

, improving previously known bounds.

Review text

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.

Recommendations

Cites work

Cited in

(14)

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)