Channel assignment and weighted coloring

In cellular telephone networks, sets of radio channels (colors) must be ass igned to transmitters (vertices) while avoiding interference. Often, the tr ansmitters are laid out like vertices of a triangular lattice in the plane. We investigated the corresponding weighted coloring problem of assigning s ets of colors to vertices of the triangular lattice so that the sets of col ors assigned to adjacent vertices are disjoint. We present a hardness resul t and an efficient algorithm yielding an approximate solution. (C) 2000 Joh n Wiley & Sons, Inc.