Alon -- Tarsi numbers of direct products

Abstract

We provide a general framework on the coefficients of the graph polynomials of graphs which are Cartesian products. As a corollary, we prove that if $G=(V,E)$ is a graph with degrees of vertices $2d(v),v\in V$, and the graph polynomial ${\prod }_{(i,j)\in E}(x_j-x_i)$ contains an "almost central" monomial (that means a monomial ${\prod }_v{x}_v^{c_v}$, where $|c_v-d(v)|⩽1$ for all $v\in V$), then the Cartesian product $G\square C_{2n}$ is $(d(\cdot )+2)$-choosable.

the proof of the main theorem is simplified in ver. 2

References in corpus (1)

• The Alon-Tarsi Number of A Toroidal Grid