Determining the Chromatic Number of a Graph
Colin McDiarmid · SIAM Journal on Computing · 1979
Certain branch-and-bound algorithms for determining the chromatic number of a graph are proved usually to take a number of steps which grows faster than exponentially with the number of vertices in the graph. A similar result holds for the number of steps in certain proofs of lower bounds for chromatic numbers.