The edge span of distance two labellings of graphs

The radio channel assignment problem can be cast as a graph coloring proble m. Vel tices correspond to transmitter locations and their labels (colors) to radio channels. The assignment of frequencies to each transmitter (verte x) must avoid interference which depends on the seperation each pair of ver tices has. Two levels of interference are assumed in the problem we are con cerned. Based on this channel assignment problem, we proposed a graph label ling problem which has two constraints instead of one. We consider the ques tion of finding the minimum edge of this labelling. Several classes of grap hs including one that is important to a telecommunication problem have been studied.