In this paper, the on-line list colouring of binomial random graphs $\mathcal{G}(n,p)$ is studied. We show that the on-line 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(n-1)$ 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 on-line 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 on-line choice number is by at most a multiplicative constant factor larger than the chromatic number.
Alan Frieze
1
;
Dieter Mitsche
2
;
Xavier Pérez-Giménez
3
;
Paweł Prałat
4
1
Department of Mathematical Sciences, Carnegie Mellon University, 5000 Forbes Av., 15213, Pittsburgh, PA, U.S.A
2
Université de Nice Sophia-Antipolis, Laboratoire J-A Dieudonné, Parc Valrose, 06108 Nice cedex 02
3
Department of Mathematics, Ryerson University, Toronto, ON, Canada
4
Department of Mathematics
Ryerson University
@article{10_37236_5003,
author = {Alan Frieze and Dieter Mitsche and Xavier P\'erez-Gim\'enez and Pawe{\l} Pra{\l}at},
title = {On-line list colouring of random graphs},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/5003},
zbl = {1327.05109},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5003/}
}
TY - JOUR
AU - Alan Frieze
AU - Dieter Mitsche
AU - Xavier Pérez-Giménez
AU - Paweł Prałat
TI - On-line list colouring of random graphs
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5003/
DO - 10.37236/5003
ID - 10_37236_5003
ER -
%0 Journal Article
%A Alan Frieze
%A Dieter Mitsche
%A Xavier Pérez-Giménez
%A Paweł Prałat
%T On-line list colouring of random graphs
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5003/
%R 10.37236/5003
%F 10_37236_5003
Alan Frieze; Dieter Mitsche; Xavier Pérez-Giménez; Paweł Prałat. On-line list colouring of random graphs. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/5003
