Conference
Version
T. Calamoneri and P. Vocca
Abstract
Given an undirected graph G, an L(h,k)-labeling of G assigns colors to vertices from the integer set {0, ...,lambda_{h,k}}, such that any two vertices v_i and v_j receive colors c(v_i) and c(v_j) satisfying the following conditions: i. if v_i and v_j are adjacent then |c(v_i)-c(v_j)|>= h; ii. if v_i and v_j are at distance two then |c(v_i)-c(v_j)| >= k. The aim of the L(h,k)-labeling problem is to minimize lambda_{h,k}. In this paper we study the approximability of the L(h,k)-labeling problem on bipartite graphs and extend the results to s-partite and general graphs. Indeed, the decision version of this problem is known to be NP-complete in general and, to our knowledge, there are no polynomial solutions, either exact or approximate, for bipartite graphs. Here, we state some results concerning the approximability of the L(h,k)-labeling problem for bipartite graphs, exploiting a novel technique, consisting in computing approximate vertex- and edge-colorings of auxiliary graphs to deduce an L(h,k)-labelling for the input bipartite graph. One of the above coloring algorithms is in fact an approximating edge-coloring algorithm for hypergraphs of maximum dimension d, i.e. the maximum edge cardinality, with performance ratio d. Furthermore, we consider a different approximation technique based on the reduction of the L(h,k)-labeling problem to the vertex-coloring of the square of a graph. These algorithms match with a result in \cite{AGH00} stating that L(1,1)-labelling n-vertex bipartite graphs is hard to approximate within n^{1/2 - epsilon}, for any epsilon > 0, unless NP=ZPP. We then extend the latter approximation strategy to $s$-partite graphs. Finally, we prove that the L(h,k)-labeling problem is not easier than coloring the square of a graph.
PDF Files