An Algorithm for the Chromatic Number of a Graph
Chung C. Wang · Journal of the ACM · 1974
Christofides' algorithm for finding the chromatic number of a graph is improved both in speed and memory space by using a depth-first search rule to search for a shortest path in a reduced subgraph tree.