Vol. 10, No. 4, 2021

Download this article
Download this article For screen
For printing
Recent Issues
Volume 13, Issue 2
Volume 13, Issue 1
Volume 12, Issue 4
Volume 12, Issue 3
Volume 12, Issue 2
Volume 12, Issue 1
Volume 11, Issue 4
Volume 11, Issue 3
Volume 11, Issue 2
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
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
founded and published with the
scientific support and advice of
mathematicians from the
Moscow Institute of
Physics and Technology
Subscriptions
 
ISSN (electronic): 2996-220X
ISSN (print): 2996-2196
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