GRAPH LABELING AND RADIO CHANNEL ASSIGNMENT

The vertex-labeling of graphs with nonnegative integers provides a nat ural setting in which to study problems of radio channel assignment. V ertices correspond to transmitter locations and their labels to radio channels. As a model for the way in which interference is avoided in r eal radio systems, each pair of vertices has, depending on their separ ation, a constraint on the difference between the labels that can be a ssigned. We consider the question of finding labelings of minimum span , given a graph and a set of constraints. The focus is on the infinite triangular lattice, infinite square lattice, and infinite line lattic e, and optimal labelings for up to three levels of constrains are obta ined. We highlight how accepted practice can lead to suboptimal channe l assignments. (C) 1998 John Wiley & Sons, Inc. J Graph Theory 29: 263 -283, 1998.