A que classe de complexidade esse idioma pertence?

Eu estava pensando em qual classe esta língua pertence: é um grafo, k é um número natural e k é o número cromático de G $L =\{ \langle G,k \rangle \mid G$$k$$k$$G\}$

Pensei em como (1) "não há coloração de k-1 cores" e (2) "não há coloração de k- cores". Agora, (1) é coNP e (2) é NP-completo, então presumo que esse idioma não esteja no NP nem no coNP, mas não encontrei a qual classe ele pertence. Qualquer ajuda será bem-vinda.$L$$k$

obrigado

$_2$$\Delta^\textrm{P}$

Um idioma L está no DP se for a interseção de um idioma L ₁ no NP com um idioma L ₂ no coNP e, portanto, seu exemplo está claramente no DP.

(como apontado por Robin, o problema está no DP ...)

... e também está completo com DP.

De fato, Jörg Rothe mostrou que isso vale para k = 4 fixo: Jörg Rothe: complexidade exata da precisão exata de quatro cores. Inf. Processo. Lett. (IPL) 87 (1): 7-12 (2003)