Almost all graphs with average degree 4 are 3-colorable
From MaRDI portal
Publication:5901043
DOI10.1145/509907.509940zbMath1192.05042OpenAlexW1971493102MaRDI QIDQ5901043
Moore, Cristopher, Demetrios Achlioptas
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509940
Related Items (5)
On the critical exponents of random k‐SAT ⋮ The probabilistic analysis of a greedy satisfiability algorithm ⋮ Exact and approximative algorithms for coloring G(n,p) ⋮ The resolution complexity of random graph \(k\)-colorability ⋮ A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
This page was built for publication: Almost all graphs with average degree 4 are 3-colorable
