A spectral technique for coloring random 3-colorable graphs (preliminary version)

DOI10.1145/195058.195187zbMath1345.05022OpenAlexW2047472567MaRDI QIDQ2817627

Nabil Kahale, Noga Alon

Publication date: 1 September 2016

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

Full work available at URL: https://doi.org/10.1145/195058.195187

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Colouring Non-sparse Random Intersection Graphs ⋮ Cryptographic hardness of random local functions. Survey ⋮ Mutual exclusion scheduling ⋮ Hardness results and spectral techniques for combinatorial problems on circulant graphs ⋮ Probabilistic analysis of local search and NP-completeness result for constraint satisfaction ⋮ Semidefinite programming and combinatorial optimization