On-line list colouring of random graphs (Q491533)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On-line list colouring of random graphs
scientific article

    Statements

    On-line list colouring of random graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    26 August 2015
    0 references
    Summary: 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 \geq (\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.
    0 references

    Identifiers