zbMATH — the first resource for mathematics

Edge-choosability in line-perfect multigraphs. (English) Zbl 0928.05017
Discrete Math. 202, No. 1-3, 191-199 (1999); erratum ibid. 260, No. 1-3, 323-326 (2003).
A multigraph is said to be line-perfect if its line graph is perfect. In this paper it is proved that if every edge \(e\) of a line-perfect multigraph \(G\) is given a list containing at least as many colors as there are edges in a largest edge-clique containing \(e\), then \(G\) can be edge-colored from its list. This leads to several characterizations of line-perfect multigraphs in terms of edge-choosability properties. It also proves that these multigraphs satisfy the list-coloring conjecture, which states that if every edge of \(G\) is given a list of \(\chi '(G)\) colors (where \(\chi ' \) denotes the chromatic index) then \(G\) can be edge-colored from its lists. Since bipartite multigraphs are line-perfect, this generalizes F. Galvin’s result [J. Comb. Theory, Ser. B 63, No. 1, 153-158 (1995; Zbl 0826.05026)] that the conjecture holds for bipartite multigraphs.

05C15 Coloring of graphs and hypergraphs
05C17 Perfect graphs
05C75 Structural characterization of families of graphs
Full Text: DOI
[1] Alon, N., Restricted colorings of graphs, (), 1-33, 1993 · Zbl 0791.05034
[2] 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
[3] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, (), 125-157
[4] Galvin, F., The List chromatic index of a bipartite multigraph, J. combin. theory ser. B, 63, 153-158, (1995) · Zbl 0826.05026
[5] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[6] Maffray, F., Kernels in perfect line-graphs, J. combin. theory ser. B, 55, 1-8, (1992) · Zbl 0694.05054
[7] Peterson, D., Choosability of perfect line graphs, (), 30-95
[8] Vizing, V.G., Vertex colorings with given colors, Metody diskret. analiz., 29, 3-10, (1976), (in Russian) · Zbl 1249.90303
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.