Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-15T04:05:54.283Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  01 September 1997

ROLAND HÄGGKVIST and
JEANNETTE JANSSEN
ROLAND HÄGGKVIST
Affiliation:
Department of Mathematics, University of Umeå, S-901 87 Umeå, Sweden (e-mail: haggkvist@mathdept.umu.se)
JEANNETTE JANSSEN
Affiliation:
Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, UK (e-mail: janssen@cdam.lse.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we show that the list chromatic index of the complete graph Kn 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](d2/3√log d).

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 3 , September 1997, pp. 295 - 313
Copyright
1997 Cambridge University Press