NPC PROBLEM minimum sum of vertex coloring
We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable?

Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are
$$
\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a &lt; b \leq 3 \}.
$$
In words, we take three copies of $G$, and connect all copies of the same vertex.

If $G$ is 3-colorable then $G'$ can be 3-colored: given a 3-coloring $\chi$ of $V$, color $(i,a)$ with the color $\chi(i) + a \bmod 3$. The sum of the colors is $6|V|$.

Conversely, suppose that $G'$ has a coloring $\chi'$ whose sum is at most $6|V|$. Note that the three copies of each vertex $(i,1),(i,2),(i,3)$ must be assigned different colors, which sum to at least $6$. Therefore $\sigma \chi' \geq 6|V|$ for any coloring $\chi'$, and $\sigma \chi' = 6|V|$ iff $\chi'$ is a 3-coloring. Considering one of the copies of $G$, we see that $G$ is 3-colorable.