On-line list colouring of random graphs

MaRDI QIDQ491533zbMATH OpenFDO

Authors D. Mitsche, Xavier Pérez-Giménez, Paweł Prałat, Alan Frieze

Publication date 26 August 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1501.07469, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p41

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this paper, the on-line list colouring of binomial random graphs G(n,p) is studied. We show that the on-line choice number of G(n,p) is asymptotically almost surely asymptotic to the chromatic number of G(n,p), provided that the average degree d=p(n-1) tends to infinity faster than (log log n)^1/3(log n)^2n^(2/3). For sparser graphs, we are slightly less successful; we show that if d>(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.

Review text

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.

Recommendations

• On-line list colouring of graphs
• List coloring of random and pseudo-random graphs
• Coloring random graphs online without creating monochromatic subgraphs
• Randomized online graph coloring
• Coloring graphs of various maximum degree from random lists

Cites work

• A note on the independence number of triangle-free graphs
• Approximating the independence number and the chromatic number in expected polynomial time
• Choice Numbers of Graphs: a Probabilistic Approach
• Choosability in random hypergraphs
• Exact and approximative algorithms for coloring G(n,p)
• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• List coloring of random and pseudo-random graphs
• Mr. Paint and Mrs. Correct
• On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
• On the chromatic number of random graphs
• On the probability of independent sets in random graphs
• On-line list colouring of graphs
• The Choice Number of Dense Random Graphs
• The chromatic number of random graphs
• The chromatic number of random graphs

Cited in

(7)

• List coloring of random and pseudo-random graphs
• On-line list colouring of graphs
• On-line and list on-line colorings of graphs and hypergraphs
• Randomized online graph coloring
• Application of polynomial method to on-line list colouring of graphs
• scientific article; zbMATH DE number 7614204 (Why is no real title available?)
• Linear colouring of binomial random graphs

This page was built for publication: On-line list colouring of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491533)