Exact complexity of Exact-Four-Colorability

✍ Scribed by Jörg Rothe

• Book ID: 104136947
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 91 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00229-1

✦ Synopsis

Let M k be a given set of k integers. Define Exact-M k -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 M k exactly. In 1987, Wagner [Theoret. Comput. Sci. 51 (1987)

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 = BH 2 (NP). Wagner raised the question of how small the numbers in a k-element set M k can be chosen such that Exact-M k -Colorability still is BH 2k (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 k 1, Exact-M k -Colorability is BH 2k (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 ∈ {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.