Why almost all k-colorable graphs are easy to color

DOI10.1007/S00224-009-9231-5zbMATH Open1216.05031OpenAlexW2170487340MaRDI QIDQ968270FDOQ968270

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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

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
• Title not available (Why is that?)

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)