k-Coloring is Faster than Computing the Chromatic NumberResearch Paper
Graph coloring is one of the basic NP-complete problems, and its exact exponential-time complexity has been studied for decades. Computing the chromatic number of an -vertex graph takes time by the inclusion–exclusion algorithm of Björklund, Husfeldt and Koivisto (SIAM J. Comput. 2009), where hides factors polynomial in the input size.…