Generalized graph coloring problems arise in connection with efficient channel assignments for networks of radio transmitters, when conditions are imposed due to different levels of interference. Such a network is represented by a simple graph G, which may be infinite. Avoiding interference leads to minimum separation requirements for channels at nearby vertices. We consider vertex labellings of G by real numbers that minimize the span of the labels used.
We have determined the optimal span for conditions at distance two for the triangular lattice and the square lattice, which are important networks for applications. We are exploring the symmetry properties of optimal labellings for the triangular lattice.
We continue to explore the general theory for infinite graphs of bounded maximum degree, where we believe the optimal span should be a piecewise linear function of the separations.
This is based on joint work with Xiaohua Teresa Jin of the University of Vermont.