ملخص: Let Mk be a given set of k integers. Define Exact-Mk-Colorability to be the problem of determining whether or not (G), the chromatic number of a given graph G, equals one of the k elements of the set Mk exactly. In 1987, Wagner [Theoret. Comput. Sci. 51 (1987) 53–80] proved that Exact-Mk-Colorability is BH2k(NP)-complete, where Mk={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 (G)=7, where DP=BH2(NP). Wagner raised the question of how small the numbers in a k-element set Mk 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 (G)=4. In this note, we solve Wagner's question and prove the optimal result: For each k1, Exact-Mk-Colorability is BH2k(NP)-complete for Mk={3k+1,3k+3,…,5k-1}. In particular, for k=1, we determine the precise threshold of the parameter t{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 (G)=4, yet Exact-{3}-Colorability is in NP.

لغة: إنجليزية