Statement

Proof

The problem is of the correct from for a search problem as you either have to provide a proper vertex k-colouring or you have to say no such colouring exists.

If you are given $G$ and a $k$-colouring $c$ it takes $O(\vert E \vert)$ time to check the colouring is proper by checking every edges vertices.