Colorings at minimum cost

We define by minc∑{u,v}∈E(G)|c(u)−c(v)|minc∑{u,v}∈E(G)|c(u)−c(v)| the min-cost  MC(G)MC(G) of a graph GG, where the minimum is taken over all proper colorings cc. The min-cost-chromatic number  χM(G)χM(G) is then defined to be the (smallest) number of colors kk for which there exists a proper kk-coloring cc attaining MC(G)MC(G). We give constructions of graphs GG where χ(G)χ(G) is arbitrarily smaller than χM(G)χM(G). On the other hand, we prove that for every 3-regular graph G′G′, χM(G′)≤4χM(G′)≤4 and for every 4-regular line graph G″G″, χM(G″)≤5χM(G″)≤5. Moreover, we show that the decision problem whether χM(G)=kχM(G)=k is NP-hard for k≥3k≥3.