# NPC PROBLEM minimum sum of vertex coloring

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.

• Sometimes you just have to sweat it. Commented May 8, 2020 at 17:40

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.