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

An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the maximum value of f(x) over all x@__ __V(G). The L(2,1)-labeling number of a graph G, denoted as @l(G), is the least integer k such that G admits an L(2,1)-labeling of span k. The problem of computing @l(G) of a graph is known to be NP-complete. Griggs and Yeh have conjectured that @l(G)=<@D^2(G) for a graph G with maximum degree, @D(G), at least two. In this paper, we propose constant approximation algorithms for the problem of computing @l(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 @l(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.