The two possible values of the chromatic number of a random graph

DOI10.1145/1007352.1007442zbMath1192.05140arXiv0706.1725OpenAlexW2164437357MaRDI QIDQ5901081

Assaf Naor, Demetrios Achlioptas

Publication date: 15 August 2010

Published in: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0706.1725

Mathematics Subject Classification ID

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

Related Items (6)

Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ Random sampling of colourings of sparse random graphs with a constant number of colours ⋮ MAX k‐CUT and approximating the chromatic number of random graphs ⋮ On the computational tractability of statistical estimation on amenable graphs ⋮ The resolution complexity of random graph \(k\)-colorability

This page was built for publication: The two possible values of the chromatic number of a random graph