Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus the diagonal entries of $D$ are all zero and $d_{ij}=d_{ji}$ so $D$ is symmetric.

Then there is a set of $k$ colors. I want to assign these colors to the $N$ nodes such that the minimum metric of a common color between any pair of nodes is maximized. So if $c(i)$ is the color assigned to $i\in [N]$ by the assignment $a\in A$, where $A$ is the set of all possible color assignments, we are looking for $$\max_{a\in A} \min_{i,j} \{d_{ij}:c(i)=c(j)\}.$$

Is this problem NP-hard? If it is, what sort of reduction can be used to show that this problem is NP-hard?

Yes. Reduce from graph coloring.

$D$ is given by $d_{i,j} = \begin{cases} 0 & \text{ if } i=j \\ 1 & \text{ if } i \text{ is adjacent to } j \\ 2 & \text{ else}\end{cases}$.

StackExchange Computer Science Q#22256, answer score: 7