To which complexity class does this language belong?
(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)