
Alan Frieze

Dieter Mitsche

Xavier PérezGiménez

Paweł Prałat
Abstract
In this paper, the online list colouring of binomial random graphs $\mathcal{G}(n,p)$ is studied. We show that the online choice number of $\mathcal{G}(n,p)$ is asymptotically almost surely asymptotic to the chromatic number of $\mathcal{G}(n,p)$, provided that the average degree $d=p(n1)$ tends to infinity faster than $(\log \log n)^{1/3} (\log n)^2 n^{2/3}$. For sparser graphs, we are slightly less successful; we show that if $d \ge (\log n)^{2+\epsilon}$ for some $\epsilon>0$, then the online choice number is larger than the chromatic number by at most a multiplicative factor of $C$, where $C \in [2,4]$, depending on the range of $d$. Also, for $d=O(1)$, the online choice number is by at most a multiplicative constant factor larger than the chromatic number.