Computing the list chromatic index of graphs

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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
Pages (from-to)182-191
Number of pages10
JournalJournal of Discrete Algorithms
Publication statusPublished - Sept 2018


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

Cite this