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$
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$
18
$\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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.