×

zbMATH — the first resource for mathematics

Computing the list chromatic index of graphs. (English) Zbl 1403.05150
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.
MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
Software:
GENREG; SageMath
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Restricted Colorings of Graphs, (Surveys in Combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes Ser., vol. 187, (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 1-33 · Zbl 0791.05034
[2] Alon, N., Combinatorial Nullstellensatz, Comb. Probab. Comput., 8, 1-2, 7-29, (1999) · Zbl 0920.05026
[3] Cariolaro, D.; Cariolaro, G.; Schauz, U.; Sun, X., The list-chromatic index of K6, Discrete Math., 322, 15-18, (2014) · Zbl 1283.05085
[4] Ellingham, M. N.; Goddyn, L., List edge colourings of some 1-factorable multigraphs, Combinatorica, 16, 343-352, (1996) · Zbl 0860.05035
[5] Galvin, F., The list chromatic index of a bipartite multigraph, J. Comb. Theory, Ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[6] 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
[7] Jensen, T. R.; Toft, B., Graph Coloring Problems, (1995), Wiley: Wiley New York · Zbl 0855.05054
[8] Kahn, J., Asymptotically good list-colorings, J. Comb. Theory, Ser. A, 73, 1, 1-59, (1996) · Zbl 0851.05081
[9] Meringer, M., Connected Regular Graphs
[10] Meringer, M., Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146, (1999) · Zbl 0918.05062
[11] Petersen, J., Die Theorie der regularen Graphs, Acta Math., 15, 193-220, (1891) · JFM 23.0115.03
[12] SageMath, The Sage Mathematics Software System (Version 7.4.1), (2017), The Sage Developers
[13] Schauz, U., Algebraically solvable problems: describing polynomials as equivalent to explicit solutions, Electron. J. Comb., 15, (2008), #R10 · Zbl 1172.13016
[14] Schauz, U., Mr. Paint and Mrs. Correct, Electron. J. Comb., 15, (2008), #R145 · Zbl 1186.05085
[15] Schauz, U., A paintability version of the combinatorial nullstellensatz, and list colorings of k-partite k-uniform hypergraphs, Electron. J. Comb., 17, 1, (2010), #R176 · Zbl 1201.05039
[16] Schauz, U., Proof of the list edge coloring conjecture for complete graphs of prime degree, Electron. J. Comb., 21, 3, (2014), #P3.43
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.