Minimise Difference

You're given a simple undirected graph $G$ with $N$ vertices and $M$ edges. You have to assign, to each vertex $i$, a number $C_i$ such that $1 \leq C_i \leq N$ and $\forall i \neq j, C_i \neq C_j$. For any such assignment, we define $D_i$ to be the number of neighbours $j$ of $i$ such that $C_j < C_i$. You want to minimise ${max_{i \in \{1..N\}} D_i} - {min_{i \in \{1..N\}} D_i}$. Output the