Colorings at minimum cost

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