-labeling of perfect elimination bipartite graphs

Abstract: An -labeling of a graph is an assignment of nonnegative integers, called colors, to the vertices of 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 -labeling is the maximum color number that has been assigned to a vertex of by . The -labeling number of a graph , denoted as , is the least integer such that has an -labeling of span . In this paper, we propose a linear time algorithm to -label a chain graph optimally. We present constant approximation -labeling algorithms for various subclasses of chordal bipartite graphs. We show that for a chordal bipartite graph , where is the maximum degree of . However, we show that there are perfect elimination bipartite graphs having . Finally, we prove that computing of a perfect elimination bipartite graph is NP-hard. [Copyright &y& Elsevier]