\(L(2,1)\)-labeling of interval graphs (Q500005)

This \(L(2, 1)\)-labeling problem is originated from an important frequency assignment application: when assigning frequency to a group of transmitters, to prevent those transmitters from interfering each other, the assignment is made with a minimum allowed separation of the frequencies. When using a graph \(G\) to represent such a transmitter network, and labeling these transmitter vertices with a number, the \(L(2, 1)\)-labeling problem is to identify \(\lambda_{2, 1}(G)\), the minimum range of such a labeling, such that the labels of two adjacent vertices of \(G\) are at least two apart, and vertices at distance two get distinct numbers. Continuing the research efforts already made on a large class of graphs, as evidenced by an impressive set of over fifty references, this paper applied an \(O(m+n)\) algorithm to construct such a labeling for an interval graph \(G(m, n),\) containing \(m\) vertices and \(n\) edges, and achieved an upper bound of \(\Delta(G)+\omega(G)\) for \(\lambda_{2, 1}(G),\) where \(\Delta(G)\) and \(\omega(G)\) represent the maximum degree and size of the maximum clique, respectively, of the graph \(G.\) This latter result is also made use of to show an upper bound of \(\Delta(G)+3\omega(G)\) for the circular-arc graphs. It is certainly (much) more challenging and interesting to make progress on the lower bound side, which needs to consider all the assignments, but not just one as constructed by an algorithm.