Tight Bounds on the Threshold for Permuted k-Colorability

DOI10.1007/978-3-642-32512-0_43zbMath1372.05068arXiv1111.2947OpenAlexW2964206502MaRDI QIDQ3167422

Moore, Cristopher, Varsha Dani, Anna Olson

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (4)

Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Circular coloring of random graphs: statistical physics investigation ⋮ Decoding from Pooled Data: Sharp Information-Theoretic Bounds

This page was built for publication: Tight Bounds on the Threshold for Permuted k-Colorability