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.
No takes yet. Share an insight, caveat, or question.
Colin McDiarmid (1979) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: