Having problem understanding the formal definition of NP
For Graph colouring problem 

Input : A graph $G(V,E)$ and $k$.

Decide : Is $G$ $k$-colourable?

Certificate : A map $\phi : V \mapsto C $, where $C = \{R,B,Y,\cdots ,P\}$ is the set of colours and $|C| = k$.

For example for any $v \in V$, $\phi(v) = Y$ means $v$ has assigned color $Y$.

Example: let complete graph $K_4 (\{v_1,v_2,v_3,v_2\},E)$ is input graph and $k=4$ i.e. is it 4-colorable? A possible certificate in this case is $\{v_1(R),v_2(B),v_3(Y),v_4(P)\}$,($v_1(R)$ means vertex $v_1$ has color $R$),  which is polynomial in input size.

Now you can see that the size of $|\phi| \le p(|G|)$, where $|G|$ is a input graph size. As you have given a map $\phi$, now you can verify in polynomial time whether colouring is valid or not.