New methods to color the vertices of a graph
- 1 April 1979
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 22 (4) , 251-256
- https://doi.org/10.1145/359094.359101
Abstract
This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.Keywords
This publication has 3 references indexed in Scilit:
- GRAPH COLORING ALGORITHMS††This research was supported in part by the Advanced Research Projects Agency of the Department of Defense under contract SD-302 and by the National Science Foundation under contract GJ-446.Published by Elsevier ,1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- An upper bound for the chromatic number of a graph and its application to timetabling problemsThe Computer Journal, 1967