Thresholds for colourability and satisfiability in random graphs and Boolean formulae

MaRDI QIDQ2741177zbMATH OpenFDO

Authors Michael Molloy

Publication date 29 March 2002

zbMATH Keywords

Boolean formulaechromatic numberscolourabilityrandom \(k\)-SATrandom graphssatisfiability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• The resolution complexity of random graph \(k\)-colorability
• scientific article; zbMATH DE number 1380613
• scientific article; zbMATH DE number 1256700

Cited in

(3)

• Research problems from the 18th British Combinatorial Conference
• The resolution complexity of random graph \(k\)-colorability
• On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs

This page was built for publication: Thresholds for colourability and satisfiability in random graphs and Boolean formulae

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