Asymptotically good list-colorings

Research output: Contribution to journalArticlepeer-review

78 Scopus citations

Abstract

The list-chromatic index, χ′l(ℋ), of a hypergraph ℋ is the least t such that for any assignment of t-sets S(A) to the edges A of ℋ, there is a proper coloring σ of ℋ with σ(A) ∈ S(A) for all A ∈ ℋ. THEOREM. Let k be fixed and ℋ a hypergraph having edges of size at most k and maximum degree D, and satisfying max{d(x, y): x, y distinct vertices of ℋ} = o(D). Then χ′l(ℋ)/D → 1 (D → ∞). Thus if edge sizes are bounded and pairwise degrees are relatively small, we have asymptotic agreement of χ′l with its trivial lower bound, the maximum degree. The corresponding result for ordinary chromatic index is a theorem of Pippenger and Spencer (J. Combin. Theory Ser. A 51 (1989), 24-42). On the other hand, even for simple graphs, earlier work falls far short of deciding the asymptotic behavior of χ′l. The "guided-random" method used in the proof is in the spirit of some earlier work and is thought to be of particular interest. One simple ingredient is a martingale inequality which ought to prove useful beyond the present context.

Original languageEnglish (US)
Pages (from-to)1-59
Number of pages59
JournalJournal of Combinatorial Theory. Series A
Volume73
Issue number1
DOIs
StatePublished - Jan 1996

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Asymptotically good list-colorings'. Together they form a unique fingerprint.

Cite this