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.



2 Answers 2


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.


(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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.