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

DOI10.1145/195058.195187MaRDI QIDQ2817627zbMATH OpenOpenAlexFDO

Authors Noga Alon, Nabil Kahalé

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

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

Recommendations

• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Exact and approximative algorithms for coloring G(n,p)
• Coloring random graphs
• Mathematical Foundations of Computer Science 2005
• Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities

Cited in

(11)

• Hardness results and spectral techniques for combinatorial problems on circulant graphs
• Mutual exclusion scheduling
• Colouring Non-sparse Random Intersection Graphs
• Cryptographic hardness of random local functions. Survey
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Coloring random graphs
• On the effect of randomness on planted 3-coloring models
• Mathematical Foundations of Computer Science 2005
• Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities
• Semidefinite programming and combinatorial optimization
• Probabilistic analysis of local search and NP-completeness result for constraint satisfaction

This page was built for publication: A spectral technique for coloring random 3-colorable graphs (preliminary version)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817627)