TY - GEN
T1 - Orientations of 1-factors and the list edge coloring conjecture
AU - Schauz, Uwe
N1 - Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Combinatorial algorithms
KW - Combinatorial nullstellensatz
KW - Edge colorings
KW - List edge coloring conjecture
KW - One-factorizations
UR - http://www.scopus.com/inward/record.url?scp=85045993716&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-78825-8_19
DO - 10.1007/978-3-319-78825-8_19
M3 - Conference Proceeding
AN - SCOPUS:85045993716
SN - 9783319788241
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 233
EP - 243
BT - Combinatorial Algorithms - 28th International Workshop, IWOCA 2017, Revised Selected Papers
A2 - Smyth, William F.
A2 - Brankovic, Ljiljana
A2 - Ryan, Joe
PB - Springer Verlag
T2 - 28th International Workshop on Combinational Algorithms, IWOCA 2017
Y2 - 17 July 2017 through 21 July 2017
ER -