11
$\begingroup$

I was thinking about which class this language belongs: $L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$

I thought of $L$ as (1) " there is no coloring of k-1 colors" and (2) "there is coloring of $k$ colors". Now, (1) is coNP and (2) is NP-complete so I assume that this language is neither in NP nor in coNP, but I didn't find to which class it belongs. Any help will be welcomed.

Thanks

$\endgroup$

2 Answers 2

14
$\begingroup$

It is contained in DP: Difference Polynomial-Time, which is also BH$_2$, the second level of the Boolean hierarchy. This class is itself contained in $\Delta^\textrm{P}$, but that is believed to be a bigger class.

A language L is in DP if it is the intersection of a language L1 in NP with a language L2 in coNP, and so your example is clearly in DP.

$\endgroup$
19
$\begingroup$

(as pointed out by Robin the problem is in DP...)

...and it is also DP-complete.

In fact, Jörg Rothe has shown that this even holds for fixed k=4: Jörg Rothe: Exact complexity of Exact-Four-Colorability. Inf. Process. Lett. (IPL) 87(1):7-12 (2003)

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy