Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-18T20:19:05.831Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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).

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)