Proof of the list edge coloring conjecture for complete graphs of prime degree
type: Item
instance of: scholarly article
title: Proof of the list edge coloring conjecture for complete graphs of prime degree
zbMATH Open document ID: 1301.05135
author: Uwe Schauz
published in: The Electronic Journal of Combinatorics
publication date: 2014-09-30T00:00:00Z
full work available at URL: v21i3p43
review text: Summary: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C07
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05E18
Mathematics Subject Classification ID: 05E99
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 6349877
zbMATH Keywords: list edge coloring
zbMATH Keywords: complete graph
zbMATH Keywords: combinatorial nullstellensatz
zbMATH Keywords: Latin square
zbMATH Keywords: paintability
MaRDI profile type: Publication
cites work: Q3142409
cites work: Combinatorial Nullstellensatz
cites work: The list-chromatic index of \(K_6\)
cites work: On the number of even and odd Latin squares of order \(p+1\)
cites work: List edge colourings of some 1-factorable multigraphs
cites work: Q3853641
cites work: New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
cites work: Brooks' theorem via the Alon-Tarsi theorem
cites work: Application of polynomial method to on-line list colouring of graphs
cites work: Q4857375
cites work: Asymptotically good list-colorings
cites work: Critically paintable, choosable or colorable graphs
cites work: Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
cites work: On the dispersions of the polynomial maps over finite fields
cites work: Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
cites work: A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
cites work: Classification of polynomial mappings between commutative groups.
cites work: How not to prove the Alon-Tarsi conjecture
cites work: Zero-sum problems for abelian \(p\)-groups and covers of the integers by residue classes
cites work: Diagonally cyclic Latin squares.
cites work: A lemma on polynomials modulo \(p^m\) and applications to coding theory
cites work: On-line list colouring of graphs
Recommended article: A list version of Dirac's theorem on the number of edges in colour-critical graphs
Recommended article: Q5143707
Recommended article: List edge and list total colourings of multigraphs
Recommended article: List edge-coloring and total coloring in graphs of low treewidth
Recommended article: On connected list colorings of graphs
Recommended article: List coloring of complete multipartite graphs
Recommended article: A note on restricted list edge-colourings
Recommended article: Q4504893
Recommended article: Partial list colouring of certain graphs
Recommended article: List edge and list total coloring of 1-planar graphs
description: scientific article; zbMATH DE number 6349877