Colouring random graphs

MaRDI QIDQ2822597zbMATH OpenFDO

Authors Ross J. Kang, Colin McDiarmid

Publication date 30 September 2016

zbMATH Keywords

chromatic numbercoloringplanar graphsrandom geometric graphsrandom graphsrandom regular graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Review text

This chapter concerns coloring of random graphs and basically answers the following two questions. Suppose that \(m\sim cn\) for some \(c\geq1/2\). Is there a positive integer function \(f=f(n)\) for which \(\chi(G_{n,m})=f\) a.a.s., and if so how large is it? What is the a.a.s. first-order approximate behavior of the chromatic number of a uniformly chosen graph with vertex-set \([n]\)? Related topics covered in this chapter include the greedy algorithm, the stability number, concentration results, the coloring rate and anti-concentration, \(k\)-colorability, etc. In addition to the classical random graph models of Erdős and Rényi, several variants including random regular graphs, random geometric graphs, and random graph models related to the coloring of planar graphs, are discussed. Some results on specific chromatic parameters such as edge and total colorings are also discussed for the dense Erdős-Rényi random graphs amongst others.NEWLINENEWLINEFor the entire collection see [Zbl 1317.05004].

Recommendations

• scientific article; zbMATH DE number 4134071
• On the chromatic number of random graphs
• The chromatic number of dense random graphs
• On the Chromatic Number of Random Graphs
• On the chromatic number of random graphs

Cited in

(18)

• Coloring random graphs
• Randomized Δ-edge colouring via exchanges of complex colours
• Coloring random graphs
• scientific article; zbMATH DE number 4134071 (Why is no real title available?)
• Randomly coloring random graphs
• Colouring Random Regular Graphs
• scientific article; zbMATH DE number 1962838 (Why is no real title available?)
• Randomly colouring graphs (a combinatorial view)
• Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors
• The Markov chain of colourings
• Finding Pseudorandom Colorings of Pseudorandom Graphs
• Non-concentration of the chromatic number of a random graph
• Coloring Random Intersection Graphs and Complex Networks
• Approximation algorithms in combinatorial scientific computing
• Colouring Random 4-Regular Graphs
• Random colorings in manifolds
• How does the chromatic number of a random graph vary?
• On the concentration of the chromatic number of random graphs

This page was built for publication: Colouring random graphs

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