Proof of the list edge coloring conjecture for complete graphs of prime degree

Uwe Schauz*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

We prove that the list-chromatic index and paintability index of Kp+1 is p; for all odd primes p: This implies that the List Edge Coloring Conjecture holds for complete graphs with less than 10 vertices. It also shows that there exist 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.

Original languageEnglish
JournalElectronic Journal of Combinatorics
Volume21
Issue number3
DOIs
Publication statusPublished - 18 Sept 2014

Fingerprint

Dive into the research topics of 'Proof of the list edge coloring conjecture for complete graphs of prime degree'. Together they form a unique fingerprint.

Cite this