Why almost all k-colorable graphs are easy to color

DOI10.1007/S00224-009-9231-5MaRDI QIDQ968270zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan, Michael Krivelevich, 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

spectral analysisrandom graphs\(k\)-colorabilityaverage case analysis

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Recommendations

• Why Almost All k-Colorable Graphs Are Easy
• Mathematical Foundations of Computer Science 2005
• Algorithms for Colouring Random k-colourable Graphs
• Almost all k-colorable graphs are easy to color
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Cites work

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

Cited in

(11)

• Constructing uniquely realizable graphs
• Average-case complexity of backtrack search for coloring sparse random graphs
• On the tractability of coloring semirandom graphs
• Planting colourings silently
• Complexity of coloring random graphs: an experimental study of the hardest region
• Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities
• The solution space structure of planted constraint satisfaction problems with growing domains
• Heuristic method to determine lucky \(k\)-polynomials for \(k\)-colorable graphs
• Almost all k-colorable graphs are easy to color
• Why Almost All k-Colorable Graphs Are Easy
• scientific article; zbMATH DE number 1670678 (Why is no real title available?)

This page was built for publication: Why almost all \(k\)-colorable graphs are easy to color

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