NPC PROBLEM minimum sum of vertex coloring

Question

For a graph G and a legal vertex-colouring ψ : V(G)→N of G,

let σψ(G) be the sum of ψ(v),

and set σ(G):=min σψ(G),

where the minimum ranges over all valid vertex colourings of G.

Prove that {(G,k): σ(G)≤ k}∈ NPC.

I thought of reduction from subset-sum but my problem is with the min and not with the sum, I don't understand how to do a reduction to check the minimum. I got a hint to do a reduction from 3-NAE-SAT but I don't understand how. would appreciate some help. even some source I can read about this problem if you know about something.

Answer 1

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 < 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.