Coloring algorithm maximising color difference between neighbors

Question

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two neighbor nodes. That is, let two neighbor nodes $i$ and $j$ colored $c_i$ and $c_j$, let $\delta_{ij}\triangleq |c_i-c_j|$, I want to find a distributed coloring algorithm that maximises the minimum of $\delta_{ij}$ of the graph. The difference between this problem with the classical distributed coloring problem is the ordered color set.

Answer 1

This is NP-hard, since we can reduce the classical distributed coloring problem to this problem (if the minimum of $\delta_{ij}$ of the graph is at least $1$, then it is $C$-colorable.