К какому классу сложности относится этот язык?

Я думал о том, к какому классу принадлежит этот язык: - граф, - натуральное число, а - хроматическое число$L =\{ \langle G,k \rangle \mid G$$k$$k$$G\}$

Я думал о как (1) «нет раскраски k-1 цветов» и (2) «есть раскраска цветов». Теперь (1) - это coNP, а (2) - NP-полная, поэтому я предполагаю, что этот язык отсутствует ни в NP, ни в coNP, но я не нашел, к какому классу он принадлежит. Любая помощь будет приветствоваться.$L$$k$

благодаря

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

Язык L находится в DP, если это пересечение языка L ₁ в NP с языком L ₂ в coNP, и поэтому ваш пример явно в DP.

(как указал Робин, проблема в DP ...)

... и это также DP-полная.

На самом деле, Йорг Роте показал, что это справедливо даже для фиксированного k = 4: Йорг Роте: Точная сложность точного четырехцветного окрашивания. Inf. Процесс. Lett. (IPL) 87 (1): 7-12 (2003)