Exact complexity of Exact-Four-Colorability

Let M-k be a given set of k integers. Define Exact-M-k-Colorability to be the problem of determining whether or not chi(G), the chromatic number of a given graph G, equals one of the k elements of the set M-k exactly. In 1987, Wagner [Theoret. Comput. Sci. 51 (1987) 53-80] proved that Exact-Mk-Colorability is BH2k (NP)-complete, where M-k = {6k + 1, 6k + 3,...,8k - 1} and BH2k (NP) is the 2kth level of the Boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not chi(G) = 7, where DP = BH2 (NP). Wagner raised the question of how small the numbers in a k-element set M-k can be chosen such that Exact-Mk-Colorability still is BH2k (NP) -complete. In particular. for k = 1. he asked if it is DP-complete to determine whether or not chi(G) = 4. In this note, we solve Wagner's question and prove the optimal result: For each k greater than or equal to 1, Exact-M-k-Colorability is BH2k (NP)-complete for M-k = {3k + 1, 3k + 3,...,5k - 1}. In particular, for k = 1, we determine the precise threshold of the parameter t is an element of {4. 5. 6. 7} for which the problem Exact-{t}-Colorability jumps from NP to DP-completeness: It is DP-complete to determine whether or not chi(G) = 4, yet Exact-(3)-Colorability is in NP. (C) 2003 Elsevier Science B.V. All rights reserved.