Vertices correspond to transmitter locations, and their labels to radio channels.
As a model for the way in which interference is avoided in real radio systems, each pair of vertices has, depending on their separation, a constraint on the difference between the labels that can be assigned. In this paper, we consider the question of finding labellings of minimum span, given a graph and a set of constraints. We focus on the infinite triangular lattice, infinite square lattice and infinite line lattice, and obtain optimal labellings for up to three levels of constraint. We highlight how accepted practice can lead to suboptimal channel assignments and also examine several open questions. CDAM Homepage .