Optimal L(δ1, δ2, 1)-labeling of eight-regular grids

Given a graph G=(V,E), an L(δ1,δ2, δ3)-labeling is a function f assigning to nodes of V colors from a set {0,1,⋯,kf} such that |f(u)-f(v) |≥δi if u and v are at distance i in G. The aim of the L(δ1,δ2,δ3)-labeling problem consists in finding a coloring function f such that the value of kf is minimum. This minimum value is called λδ1, δ2,δ3(G). In this paper we study this problem on the eight-regular grids for the special values (δ1, δ2,δ3)=(3,2,1) and (δ1, δ2,δ3)=(2,1,1), providing optimal labelings. Furthermore, exploiting the lower bound technique, we improve the known lower bound on λ3,2,1 for triangular grids. © 2013 Elsevier B.V. All rights reserved.