L(2,1)L(2,1)-labeling of dually chordal graphs and strongly orderable graphs

An L(2,1)L(2,1)-labeling   of a graph G=(V,E)G=(V,E) is a function f:V(G)→{0,1,2,…}f:V(G)→{0,1,2,…} such that |f(u)−f(v)|⩾2|f(u)−f(v)|⩾2 whenever uv∈E(G)uv∈E(G) and |f(u)−f(v)|⩾1|f(u)−f(v)|⩾1 whenever u and v are at distance two apart. The span   of an L(2,1)L(2,1)-labeling f of G  , denoted as SP2(f,G)SP2(f,G), is the maximum value of f(x)f(x) over all x∈V(G)x∈V(G). The L(2,1)L(2,1)-labeling number of a graph G  , denoted as λ(G)λ(G), is the least integer k such that G   admits an L(2,1)L(2,1)-labeling of span k  . The problem of computing λ(G)λ(G) of a graph is known to be NP-complete. Griggs and Yeh have conjectured that λ(G)⩽Δ2(G)λ(G)⩽Δ2(G) for a graph G   with maximum degree, Δ(G)Δ(G), at least two. In this paper, we propose constant approximation algorithms for the problem of computing λ(G)λ(G) for dually chordal graphs and strongly orderable graphs. As a by-product, we prove Griggs and Yeh Conjecture for dually chordal graphs and for those strongly orderable graphs whose maximum degrees are different from three. Finally, we propose a 2-approximation algorithm for computing λ(G)λ(G) for chordal bipartite graphs, a special subclass of strongly orderable graphs, and prove that Griggs and Yeh Conjecture holds true for this class of graphs.

► We propose constant approximation algorithms for computing λ(G)λ(G) for dually chordal graphs.
► We propose constant approximation algorithms for computing λ(G)λ(G) for strongly orderable graphs.
► We prove Griggs and Yeh Conjecture for dually chordal graphs and for chordal bipartite graphs.
► We propose a 2-approximation algorithm for computing λ(G)λ(G) for chordal bipartite graphs.
► We prove Griggs and Yeh Conjecture for strongly orderable graphs for which Δ≠3Δ≠3.