The L(3,2,1)-labeling on Bipartite Graphs

An L(3, 2, 1)-labeling of a graph G is a function from the vertex set V (G) to the set of all nonnegative integers such that |f(u) - f(v)| ≥ 3 if dG(u, v) = 1, |f(u) - f(v)| ≥ 2 if dG(u,v) = 2, and |f(u) - f(v)| ≥ 1 if dG(u,v) = 3. The L(3, 2, 1)-labeling problem is to find the smallest number λ3(G) such that there ex- ists an L(3, 2, 1)-labeling function with no label greater than it. This paper studies the problem for bipartite graphs. We obtain some bounds of λ3 for bipartite graphs and its subclasses. Moreover, we provide a best possible condition for a tree T such that λ3(T ) attains the minimum value.