zbMATH — the first resource for mathematics

New bounds on the list-chromatic index of the complete graph and other simple graphs. (English) Zbl 0880.05035
The list chromatic index of a graph \(G\) is the smallest integer \(t\) such that if we assign an arbitrary list of \(t\) colours to the edges of \(G\) there always exists an edge-colouring for which every edge receives a colour from its list and every colour class is a matching. In this paper it is shown that the list chromatic index of the complete graph \(K_n\) is at most \(n\). This proves the list chromatic conjecture for complete graphs of odd order. The following asymptotic result is also proved; that for a simple graph with maximum degree \(d\) the list chromatic index exceeds \(d\) by at most \(O(d^{2/3}\sqrt{\log d})\).

05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI