Between Colorings and Layouts - Minimum Morphism Cost Problems 1

For a graph G, we define the minimum morphism cost of the graph MC(G) as mink{minϕ:V→[k]∑{u,v}∈E|ϕ(u)−ϕ(v)|} with the condition that for any {u,v}∈E we must have ϕ(u)≠ϕ(v). The morphism-chromatic number χM(G) is then defined to be the (smallest) value of k for which MC(G) is attained. We give constructions of graphs where χM(G) is arbitrarily smaller than χM(G). On the other hand, we prove that for all 3-regular graphs and for 4-regular graphs with some restrictions, χM(G)⩽χ(G)+1.