Degrees and choice numbers

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

The choice number ch(G) of a graph G = (V, E) is the minimum number k such that for every assignment of a list S(ν) of at least k colors to each vertex ν ∈ V, there is a proper vertex coloring of G assigning to each vertex ν a color from its list S(ν). We prove that if the minimum degree of G is d, then its choice number is at least (1/2 - 0(1)) log2 d, where the 0(1)-term tends to zero as d tends to infinity. This is tight up to a constant factor of 2 + 0(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich.

Original languageEnglish (US)
Pages (from-to)364-368
Number of pages5
JournalRandom Structures and Algorithms
Volume16
Issue number4
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Degrees and choice numbers'. Together they form a unique fingerprint.

Cite this