Orientations of 1-factors and the list edge coloring conjecture

Uwe Schauz*

*Corresponding author for this work

Research output: Chapter in Book or Report/Conference proceedingConference Proceedingpeer-review


As starting point, we formulate a corollary to the Quantitative Combinatorial Nullstellensatz. This corollary does not require the consideration of any coefficients of polynomials, only evaluations of polynomial functions. In certain situations, our corollary is more directly applicable and more ready-to-go than the Combinatorial Nullstellensatz itself. It is also of interest from a numerical point of view. We use it to explain a well-known connection between the sign of 1-factorizations (edge colorings) and the List Edge Coloring Conjecture. For efficient calculations and a better understanding of the sign, we then introduce and characterize the sign of single 1-factors. We show that the product over all signs of all the 1-factors in a 1-factorization is the sign of that 1-factorization. Using this result in an algorithm, we attempt to prove the List Edge Coloring Conjecture for all graphs with up to 10 vertices. This leaves us with some exceptional cases that need to be attacked with other methods.

Original languageEnglish
Title of host publicationCombinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
EditorsWilliam F. Smyth, Ljiljana Brankovic, Joe Ryan
PublisherSpringer Verlag
Number of pages11
ISBN (Print)9783319788241
Publication statusPublished - 2018
Event28th International Workshop on Combinational Algorithms, IWOCA 2017 - Newcastle, NSW, Australia
Duration: 17 Jul 201721 Jul 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10765 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference28th International Workshop on Combinational Algorithms, IWOCA 2017
CityNewcastle, NSW


  • Combinatorial algorithms
  • Combinatorial nullstellensatz
  • Edge colorings
  • List edge coloring conjecture
  • One-factorizations

Cite this