The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic

DOI10.1088/0305-4470/36/43/027zbMath1072.05575arXivcond-mat/0304606OpenAlexW3106065224MaRDI QIDQ5696396

Liat Ein-Dor, Remi Monasson

Publication date: 18 October 2005

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

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

zbMATH Keywords

surface growthuncolourabilitybacktracking produce

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Complexity of Coloring Random Graphs ⋮ Average-case complexity of backtrack search for coloring sparse random graphs ⋮ The resolution complexity of random graph \(k\)-colorability

This page was built for publication: The dynamics of proving uncolourability of large random graphs: I. Symmetric colouring heuristic