Premium
Asymptotics of the list‐chromatic index for multigraphs
Author(s) -
Kahn Jeff
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200009)17:2<117::aid-rsa3>3.0.co;2-9
Subject(s) - multigraph , edge coloring , mathematics , chromatic scale , index (typography) , combinatorics , bounded function , set (abstract data type) , discrete mathematics , computer science , graph , mathematical analysis , line graph , world wide web , graph power , programming language
The list‐chromatic index , χ l ′( G ) of a multigraph G is the least t such that if S ( A ) is a set of size t for each A ∈ E ≔ E ( G ), then there exists a proper coloring σ of G with σ( A )∈ S ( A ) for each A ∈ E . The list‐chromatic index is bounded below by the ordinary chromatic index, χ′( G ), which in turn is at least the fractional chromatic index, χ′*( G ). In previous work we showed that the chromatic and fractional chromatic indices are asymptotically the same; here we extend this to the list‐chromatic index: χ l ′( G )∼χ′*( G ) as χ l ′( G )→∞. The proof uses sampling from “hard‐core” distributions on the set of matchings of a multigraph to go from fractional to list colorings. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 117–156, 2000