Channel assignment and multicolouring of the induced subgraphs of the triangular lattice

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. Often the transmitters are laid out like vertices of a triangular lattice in the plane. We investigate the corresponding colouring problem of assigning sets of colours of given size k to vertices of the triangular lattice so that the sets of colours assigned to adjacent vertices are disjoint. We prove here that every triangle-free induced subgraph of the triangular lattice is [7k/3] -[k]colourable. That means that it is possible to assign to each transmitter of such a network, k bands of a set of [7k/3], so that there is no interference. (C) 2001 Elsevier Science B.V. All rights reserved.