New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs

Abstract

In this paper we show 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. We also prove the asymptotic result that for a simple graph with maximum degree d the list chromatic index exceeds d by at most [Oscr ]( d 2/3 √log d ).