Alon–Tarsi numbers of direct products

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 $2 d (v)$ , $v \in V$ , and the graph polynomial $\prod_{(i, j) \in E} (x_{j} - x_{i})$ contains an “almost central” monomial (that is a monomial $\prod_{v} x_{v}^{c_{v}}$ , where $| c_{v} - d (v) | \leq 1$ for all $v \in V$ ), then the Cartesian product $G □ C_{2 n}$ is $(d (\cdot) + 2)$ -choosable.

PDF Access Denied

We have not been able to recognize your IP address 18.222.23.119 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 40.00:

Keywords

combinatorial Nullstellensatz, list coloring, Alon–Tarsi number

Mathematical Subject Classification

Primary: 05C15, 05D40

Milestones

Received: 5 February 2021

Revised: 5 October 2021

Accepted: 20 October 2021

Published: 17 January 2022

Authors

Fedor Petrov
St. Petersburg State University St. Petersburg Russia

Alexey Gordeev
The Euler International Mathematical Institute St. Petersburg Russia

Vol. 10, No. 4, 2021

Fedor Petrov and Alexey Gordeev

Abstract

PDF Access Denied

Keywords

Mathematical Subject Classification

Milestones

Authors