Vol. 10, No. 4, 2021

Download this article
Download this article For screen
For printing
Recent Issues
Volume 11, Issue 1
Volume 10, Issue 4
Volume 10, Issue 3
Volume 10, Issue 2
Volume 10, Issue 1
Volume 9, Issue 4
Volume 9, Issue 3
Volume 9, Issue 2
Volume 9, Issue 1
Volume 8, Issue 4
Volume 8, Issue 3
Volume 8, Issue 2
Volume 8, Issue 1
Older Issues
Volume 7, Issue 4
Volume 7, Issue 3
Volume 7, Issue 2
Volume 7, Issue 1
Volume 6, Issue 4
Volume 6, Issue 2-3
Volume 6, Issue 1
Volume 5, Issue 4
Volume 5, Issue 3
Volume 5, Issue 1-2
Volume 4, Issue 4
Volume 4, Issue 3
Volume 4, Issue 2
Volume 4, Issue 1
Volume 3, Issue 3-4
Volume 3, Issue 2
Volume 3, Issue 1
Volume 2, Issue 4
Volume 2, Issue 3
Volume 2, Issue 2
Volume 2, Issue 1
Volume 1, Issue 4
Volume 1, Issue 3
Volume 1, Issue 2
Volume 1, Issue 1
The Journal
About the Journal
Editorial Board
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
 
ISSN (electronic): 2640-7361
ISSN (print): 2220-5438
Author Index
To Appear
 
Other MSP Journals
Alon–Tarsi numbers of direct products

Fedor Petrov and Alexey Gordeev

Vol. 10 (2021), No. 4, 271–279
DOI: 10.2140/moscow.2021.10.271
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 V, and the graph polynomial (i,j)E(xj xi) contains an “almost central” monomial (that is a monomial vxvcv, where |cv d(v)| 1 for all v V ), then the Cartesian product G C2n is (d( ) + 2)-choosable.

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