# Statement

# Proof

The problem is of the correct form 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 each edge’s endpoints.