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

• Optimal L(3,2,1)-labeling for ERGs.
• Optimal L(2,1,1)-labeling for ERGs.
• Improved lower bound on the λ3,2,1-number for triangular 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.