Why Almost All k-Colorable Graphs Are Easy

DOI10.1007/978-3-540-70918-3_11zbMath1186.05050MaRDI QIDQ3590926

Michael Krivelevich, Amin Coja-Oghlan, Dan Vilenchik

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_11

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A Spectral Method for MAX2SAT in the Planted Solution Model