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

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

Michael Krivelevich, Dan Vilenchik, Amin Coja-Oghlan

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 graphsspectral analysisaverage case analysis\(k\)-colorability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items

The solution space structure of planted constraint satisfaction problems with growing domains, Constructing uniquely realizable graphs, Average-case complexity of backtrack search for coloring sparse random graphs

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