Thats a unique idea.You should consider the following idea to enhance your idea so that it would impact uniquely: 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,  solve Wagner's question and prove the optimal result: For each k ≥ 1, Exact-Mk-Colorability is BH2k(NP)-complete for Mk = {3k + 1, 3k + 3 ..., 5k - 1}. In particular, for k = 1,  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.
['Jörg Rothe']
I am writing a research paper on a idea Exact complexity of exact-four-colorability
[{"from": "human", "value": "I am writing a research paper on a idea Exact complexity of exact-four-colorability"}, {"from": "gpt", "value": "Thats a unique idea.You should consider the following idea to enhance your idea so that it would impact uniquely: Let Mk be a given set of k integers. Define Exact-Mk-Colorability to be the problem of determining whether or not \u03c7(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 \u03c7(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 \u03c7(G) = 4.In this note,  solve Wagner's question and prove the optimal result: For each k \u2265 1, Exact-Mk-Colorability is BH2k(NP)-complete for Mk = {3k + 1, 3k + 3 ..., 5k - 1}. In particular, for k = 1,  determine the precise threshold of the parameter t \u2208 {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 \u03c7(G) = 4, yet Exact-{3}-Colorability is in NP."}]