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

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