Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)L(p,q)-labeling of a graph GG is an assignment ff from vertices of GG to the set of non-negative integers {0,1,…,λ}{0,1,…,λ} such that |f(u)−f(v)|≥p|f(u)−f(v)|≥p if uu and vv are adjacent, and |f(u)−f(v)|≥q|f(u)−f(v)|≥q if uu and vv are at distance 2 apart. The minimum value of λλ for which GG has L(p,q)L(p,q)-labeling is denoted by λp,q(G)λp,q(G). The L(p,q)L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)L(p,q)-labeling of a bipartite permutation graph GG such that the largest label is at most (2p−1)+q(bc(G)−2)(2p−1)+q(bc(G)−2), where bc(G)bc(G) is the biclique number of GG. Since λp,q(G)≥p+q(bc(G)−2)λp,q(G)≥p+q(bc(G)−2) for any bipartite graph GG, the upper bound is at most p−1p−1 far from optimal.