An Algorithm for Determining the Chromatic Number of a Graph
Derek Gordon Corneil, B. T. Graham · SIAM Journal on Computing · 1973
A heuristic algorithm for the determination of the chromatic number of a finite graph is presented. This algorithm is based on Zykov’s theorem for chromatic polynomials, and extensive empirical tests show that it is the best algorithm available. Christofides’ algorithm for the determination of chromatic number is described and is used in the comparison tests.