List edge multicoloring in graphs with few cycles. (English) Zbl 1183.68433
Summary: The list edge multicoloring problem is a version of edge coloring where every edge \(e\) has a list of available colors \(L(e)\) and an integer demand \(x(e)\). For each \(e\), we have to select \(x(e)\) colors from \(L(e)\) such that adjacent edges receive disjoint sets of colors. Marcotte and Seymour proved a characterization theorem for list edge multicoloring trees, which can be turned into a polynomial time algorithm. We present a slightly more general algorithm that works also on odd cycles. A variant of the method leads to a randomized polynomial time algorithm for handling even cycles as well.
References:
| [1] | Colbourn, C. J., The complexity of completing partial Latin squares, Discrete Appl. Math., 8, 1, 25-30 (1984) · Zbl 0538.05013 |
| [2] | Hopcroft, J. E.; Karp, R. M., An \(n^{5/2}\) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 2, 225-231 (1973) · Zbl 0266.05114 |
| [3] | Klostermeyer, W. F.; Goldwasser, J. L., List multi-coloring problems, Bull. Inst. Combin. Appl., 34, 71-76 (2002) · Zbl 0995.05060 |
| [4] | Kratochvı́l, J., Precoloring extension with fixed color bound, Acta Math. Univ. Comenian., 62, 2, 139-153 (1993) · Zbl 0821.05027 |
| [5] | Lovász, L.; Plummer, M. D., Matching Theory. Matching Theory, Annals of Discrete Mathematics, 29 (1986), North-Holland: North-Holland Amsterdam · Zbl 0618.05001 |
| [6] | Marcotte, O.; Seymour, P. D., Extending an edge-coloring, J. Graph Theory, 14, 5, 565-573 (1990) · Zbl 0705.05031 |
| [7] | Marx, D., The complexity of tree multicolorings, (Mathematical Foundations of Computer Science 2002 (Warsaw-Otwock) (2002), Springer: Springer Berlin), 532-542 · Zbl 1014.68117 |
| [8] | Micali, S.; Vazirani, V. V., An \(O(|V||E|)\) algorithm for finding maximum matching in general graphs, (21st Annual Symp. on Foundations of Computer Science, Syracuse, NY (1980)), 17-27 |
| [9] | Mulmuley, K.; Vazirani, U. V.; Vazirani, V. V., Matching is as easy as matrix inversion, Combinatorica, 7, 1, 105-113 (1987) · Zbl 0632.68041 |
| [10] | Tuza, Z., Graph colorings with local constraints—a survey, Discuss. Math. Graph Theory, 17, 2, 161-228 (1997) · Zbl 0923.05027 |
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.
