Why almost all \(k\)-colorable graphs are easy to color

DOI10.1007/s00224-009-9231-5zbMath1216.05031MaRDI QIDQ968270

Michael Krivelevich, Amin Coja-Oghlan, Dan Vilenchik

Publication date: 5 May 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9231-5

zbMATH Keywords

random graphs; spectral analysis; average case analysis; \(k\)-colorability

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zero knowledge and the chromatic number
• Heuristics for semirandom graph problems
• Pairs of SAT-assignments in random Boolean formulæ
• Coloring Random Graphs
• The solution of some random NP-hard problems in polynomial expected time
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems
• Almost all k-colorable graphs are easy to color
• Random I‐colorable graphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring Random and Semi-Random k-Colorable Graphs
• Survey propagation: An algorithm for satisfiability
• Spectral techniques applied to sparse random graphs
• Probability Inequalities for Sums of Bounded Random Variables
• Automata, Languages and Programming
• Mathematical Foundations of Computer Science 2005
• On the solution-space geometry of random constraint satisfaction problems
• The chromatic number of random graphs
• The chromatic number of random graphs