Proof of the list edge coloring conjecture for complete graphs of prime degree
The electronic journal of combinatorics, Tome 21 (2014) no. 3
We prove that the list-chromatic index and paintability index of $K_{p+1}$ is $p$, for all odd primes $p$. This implies that the List Edge Coloring Conjecture holds for complete graphs with less then 10 vertices. It also shows that there are arbitrarily big complete graphs for which the conjecture holds, even among the complete graphs of class 1. Our proof combines the Quantitative Combinatorial Nullstellensatz with the Paintability Nullstellensatz and a group action on symmetric Latin squares. It displays various ways of using different Nullstellensätze. We also obtain a partial proof of a version of Alon and Tarsi's Conjecture about even and odd Latin squares.
DOI :
10.37236/4084
Classification :
05C15, 05C07, 05B15, 05E18, 05E99, 05A19, 91A43
Mots-clés : list edge coloring, complete graph, combinatorial nullstellensatz, Latin square, paintability
Mots-clés : list edge coloring, complete graph, combinatorial nullstellensatz, Latin square, paintability
Affiliations des auteurs :
Uwe Schauz 1
@article{10_37236_4084,
author = {Uwe Schauz},
title = {Proof of the list edge coloring conjecture for complete graphs of prime degree},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4084},
zbl = {1301.05135},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4084/}
}
Uwe Schauz. Proof of the list edge coloring conjecture for complete graphs of prime degree. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4084
Cité par Sources :