×

Orientations of 1-factors and the list edge coloring conjecture. (English) Zbl 1507.05042

Brankovic, Ljiljana (ed.) et al., Combinatorial algorithms. 28th international workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17–21, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10765, 233-243 (2018).
Summary: 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.
For the entire collection see [Zbl 1386.68003].

MSC:

05C15 Coloring of graphs and hypergraphs

References:

[1] Alon, N.: Restricted colorings of graphs. In: Surveys in Combinatorics. London Mathematical Society Lecture Notes Series, vol. 187, pp. 1-33. Cambridge University Press, Cambridge (1993) · Zbl 0791.05034
[2] Alon, N., Combinatorial nullstellensatz, Comb. Probab. Comput., 8, 1-2, 7-29, 1999 · Zbl 0920.05026 · doi:10.1017/S0963548398003411
[3] Ellingham, MN; Goddyn, L., List edge colourings of some 1-factorable multigraphs, Combinatorica, 16, 343-352, 1996 · Zbl 0860.05035 · doi:10.1007/BF01261320
[4] Galvin, F., The list chromatic index of a bipartite multigraph, J. Comb. Theory Ser. B, 63, 153-158, 1995 · Zbl 0826.05026 · doi:10.1006/jctb.1995.1011
[5] Häggkvist, R.; Janssen, J., New bounds on the list-chromatic index of the complete graph and other simple graphs, Comb. Probab. Comput., 6, 295-313, 1997 · Zbl 0880.05035 · doi:10.1017/S0963548397002927
[6] Jensen, TR; Toft, B., Graph Coloring Problems, 1995, New York: Wiley, New York · Zbl 0855.05054
[7] Kahn, J., Asymptotically good list-colorings, J. Comb. Theory Ser. A, 73, 1, 1-59, 1996 · Zbl 0851.05081 · doi:10.1006/jcta.1996.0001
[8] Meringer, M.: Connected regular graphs. http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html
[9] Meringer, M., Fast generation of regular graphs and construction of cages, J. Gr. Theory, 30, 137-146, 1999 · Zbl 0918.05062 · doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G
[10] Petersen, J., Die theorie der regularen graphs, Acta Math., 15, 193-220, 1891 · JFM 23.0115.03 · doi:10.1007/BF02392606
[11] SageMath: The sage mathematics software system (version 7.4.1). The Sage Developers (2017). http://www.sagemath.org
[12] Schauz, U., Algebraically solvable problems: describing polynomials as equivalent to explicit solutions, Electron. J. Comb., 15, R10, 2008 · Zbl 1172.13016
[13] Schauz, U., Mr. Paint and Mrs. Correct, Electron. J. Comb., 15, R145, 2008
[14] Schauz, U., A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs, Electron. J. Comb., 17, 1, R176, 2010 · Zbl 1201.05039
[15] Schauz, U., Proof of the list edge coloring conjecture for complete graphs of prime degree, Electron. J. Comb., 21, 3, 3-43, 2014 · Zbl 1301.05135
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.