zbMATH — the first resource for mathematics

Edge-choosability of multicircuits. (English) Zbl 0928.05018
Author’s abstract: A multicircuit is a multigraph whose underlying simple graph is a circuit (a connected 2-regular graph). The list-colouring conjecture (LCC) is that every multigraph \(G\) has edge-choosability (list chromatic index) \(\text{ch}'(G)\) equal to its chromatic index \(\chi '(G)\). In this paper the LCC is proved first for multicircuits, and then, building on results of Peterson and Woodall [cf. Zbl 0928.05012 above], for any multigraph \(G\) in which every block is bipartite or a multicircuit or has at most four vertices or has underlying simple graph of the form \(K_{1,1,p}\).

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., List edge and List total colourings of multigraphs, J. combin. theory ser. B, 71, 184-204, (1997) · Zbl 0876.05032
[2] O.V. Borodin, A.V. Kostochka, D.R. Woodall, On kernel-perfect orientiations of line graphs, Discrete Math., to appear. · Zbl 0955.05049
[3] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[4] Häggkvist, R.; Chetwynd, A., Some upper bounds on the total and List chromatic numbers of multigraphs, J. graph theory, 16, 503-516, (1992) · Zbl 0814.05038
[5] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0971.05046
[6] Maffray, F., Kernels in perfect line-graphs, J. combin. theory ser. B, 55, 1-8, (1992) · Zbl 0694.05054
[7] Peterson, D.; Woodall, D.R., Edge-choosability in line-perfect multigraphs, Discrete math., 202, 191-199, (1999), (this Vol.) · Zbl 0928.05017
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.