A strengthening and an efficient implementation of Alon-Tarsi list coloring method
The electronic journal of combinatorics, Tome 31 (2024) no. 1
As one of the first applications of the polynomial method in combinatorics, Alon and Tarsi proved that if certain coefficients of the graph polynomial are non-zero, then the graph is choosable, i.e., colorable from any assignment of lists of prescribed size. We show that in case all relevant coefficients are zero, then further coefficients of the graph polynomial provide constraints on the list assignments from which the graph cannot be colored. This often enables us to confirm colorability from a given list assignment, or to decide choosability by testing just a few list assignments. We also describe an efficient way to implement this approach, making it feasible to test choosability of graphs with around 70 edges.
DOI :
10.37236/12058
Classification :
05C15, 05C85
Mots-clés : polynomial method, orientations, chromatic number, vertex-coloring
Mots-clés : polynomial method, orientations, chromatic number, vertex-coloring
Affiliations des auteurs :
Zdeněk Dvořák 1
@article{10_37236_12058,
author = {Zden\v{e}k Dvo\v{r}\'ak},
title = {A strengthening and an efficient implementation of {Alon-Tarsi} list coloring method},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/12058},
zbl = {1533.05089},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12058/}
}
Zdeněk Dvořák. A strengthening and an efficient implementation of Alon-Tarsi list coloring method. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/12058
Cité par Sources :