A note on coloring sparse random graphs

DOI10.1016/j.disc.2008.09.038zbMath1185.05128OpenAlexW2145374630MaRDI QIDQ1025963

Christian Sommer

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.09.038

zbMATH Keywords

combinatorial problemsanalysis of algorithmsgraph coloring algorithmrandom graphsgenerating function

Mathematics Subject Classification ID

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

Related Items (4)

Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Computing the eccentricity distribution of large graphs ⋮ Uncertain vertex coloring problem ⋮ An uncertain chromatic number of an uncertain graph based on \(\alpha \)-cut coloring

Cites Work

• Unnamed Item
• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A note on the complexity of the chromatic number problem
• Zero knowledge and the chromatic number
• Sudden emergence of a giant \(k\)-core in a random graph
• 3-coloring in time
• Exact and approximative algorithms for coloring G(n,p)
• Random Graphs

This page was built for publication: A note on coloring sparse random graphs