Between Colorings and Layouts - Minimum Morphism Cost Problems

For a graph G, we define the minimum morphism cost of the graph M C ( G ) as min k { 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 M C ( 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 .