Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

DOI10.1007/B99805zbMath1105.05063arXivcond-mat/0407278OpenAlexW4301133941MaRDI QIDQ5313025

Moore, Cristopher, Demetrios Achlioptas

Publication date: 25 August 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0407278

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15)

Related Items (14)

Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ Planting Colourings Silently ⋮ The cook-book approach to the differential equation method ⋮ Two notions of unit distance graphs ⋮ Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models ⋮ On the chromatic number of the preferential attachment graph ⋮ An upper bound on adaptable choosability of graphs ⋮ MAX k‐CUT and approximating the chromatic number of random graphs ⋮ The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ On the chromatic number of random \(d\)-regular graphs ⋮ Random regular graphs of non-constant degree: concentration of the chromatic number ⋮ The Ising Antiferromagnet and Max Cut on Random Regular Graphs ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

This page was built for publication: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques