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 language||English (US)|
|Number of pages||5|
|Journal||Random Structures and Algorithms|
|State||Published - Jan 1 2000|
All Science Journal Classification (ASJC) codes
- Applied Mathematics
- Computer Graphics and Computer-Aided Design