Almost all k-colorable graphs are easy to color
- 31 March 1988
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 9 (1) , 63-82
- https://doi.org/10.1016/0196-6774(88)90005-3
Abstract
No abstract availableKeywords
This publication has 7 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- A theoretical analysis of backtracking in the graph coloring problemJournal of Algorithms, 1985
- Backtrack: An O(1) expected time algorithm for the graph coloring problemInformation Processing Letters, 1984
- Improving the performance guarantee for approximate graph coloringJournal of the ACM, 1983
- Fast probabilistic algorithms for hamiltonian circuits and matchingsJournal of Computer and System Sciences, 1979
- New methods to color the vertices of a graphCommunications of the ACM, 1979
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976