Witness on the upper bound of chromatic (choice) number
of
random graphs
Van Vu
It is well known that almost every graph in the random space
$G(n,p)$
has chromatic number of order $O (np/ \log (np))$,
but it is not clear how we can recognize such graphs without eventually
computing the chromatic numbers, which is NP-hard. The first
goal of this paper is to show
that the above mentioned upper bound
on the chromatic number can be guaranteed by simple degree conditions,
which are satisfied by $G(n,p)$ almost surely
for most values of $p$. It turns out that the same conditions imply
a similar bound for the choice number of a graph.
Our result has several applications related to the asymptotic behavior of
the choice number of random graphs and
locally sparse graphs and to partitions of finite fields. Most of the results
can be obtained by polynomial (randomized) algorithms.