L(2,1)L(2,1)-labeling of perfect elimination bipartite graphs

An L(2,1)L(2,1)-labeling of a graph GG is an assignment of nonnegative integers, called colors, to the vertices of GG such that the difference between the colors assigned to any two adjacent vertices is at least two and the difference between the colors assigned to any two vertices which are at distance two apart is at least one. The span of an L(2,1)L(2,1)-labeling ff is the maximum color number that has been assigned to a vertex of GG by ff. The L(2,1)L(2,1)-labeling number of a graph GG, denoted as λ(G)λ(G), is the least integer kk such that GG has an L(2,1)L(2,1)-labeling of span kk. In this paper, we propose a linear time algorithm to L(2,1)L(2,1)-label a chain graph optimally. We present constant approximation L(2,1)L(2,1)-labeling algorithms for various subclasses of chordal bipartite graphs. We show that λ(G)=O(Δ(G))λ(G)=O(Δ(G)) for a chordal bipartite graph GG, where Δ(G)Δ(G) is the maximum degree of GG. However, we show that there are perfect elimination bipartite graphs having λ=Ω(Δ2)λ=Ω(Δ2). Finally, we prove that computing λ(G)λ(G) of a perfect elimination bipartite graph is NP-hard.