Advertisement
Published in:
2017 | OriginalPaper | Chapter
On-Line List Colouring of Random Graphs
Authors : Alan Frieze, Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałat
Published in: Extended Abstracts Summer 2015
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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 (loglogn)1∕3(logn)2
n
2∕3. For sparser graphs, we are slightly less successful; we show that if d ≥ (logn)2+ɛ
for some ɛ > 0, then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C, where C ∈ [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.