zbMATH — the first resource for mathematics

A note on list-colorings. (English) Zbl 0674.05026
Let G be a multigraph and assign to every edge e in G some set f(e) of, say, m colors. The list-chromatic index \(\chi '_{\ell}(G)\) is the smallest m that guarantees an f-edge-coloring of G, i.e., a coloring of the edges of G such that no pair of adjacent edges have the same color, and moreover, every edge e has a color from its list f(e).
The main result of this paper is that \(\chi '_{\ell}(G)\leq 9\Delta /5\) for every triangle-free graph G with maximum degree \(\Delta\).
Reviewer: I.Tomescu

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] The total chromatic number of a graph: a survey, Combinatorial Mathematics and Its Applications, Proceedings of the Conference in Oxford, 1969, Academic Press, New York (1971) 1–9.
[2] Bollobás, Graphs Combinat. 1 pp 115– (1985)
[3] Erdös, Congressus Numerantum 23 pp 19– (1979)
[4] Erdös, Congressus Numerantum 26 pp 125– (1979)
[5] Restricted edge-colorings of bipartite graphs, manuscript.
[6] doctoral thesis.
[7] An upper bound for the total chromatic number, manuscript.
[8] Coloring the vertices of a graph in prescribed colors (Russian), Diskret. Analiz No 29 Metody Diskret. Anal. v Teorii Kodov i Shem (1976) 3–10, 101 (MR58#16371).
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.