A Spectral Technique for Coloring Random 3-Colorable Graphs
- 1 December 1997
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 26 (6) , 1733-1748
- https://doi.org/10.1137/s0097539794270248
Abstract
No abstract availableThis publication has 9 references indexed in Scilit:
- On triangle-free random graphsRandom Structures & Algorithms, 2000
- An algorithm for 3-colorable graphsInformation Processing Letters, 1997
- Coloring Random and Semi-Random k-Colorable GraphsJournal of Algorithms, 1995
- On the second eigenvalue and random walks in randomd-regular graphsCombinatorica, 1991
- A randomised 3-colouring algorithmDiscrete Mathematics, 1989
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- Almost all k-colorable graphs are easy to colorJournal of Algorithms, 1988
- Graph Coloring Using Eigenvalue DecompositionSIAM Journal on Algebraic Discrete Methods, 1984
- The eigenvalues of random symmetric matricesCombinatorica, 1981