Bounds for the frequency assignment problem

The problem of assigning radio frequencies to a set of transmitters in a region is related to the theory of vertex colourings of graphs. Real frequency assignment problems often deal with a large number of transmitters. Exact methods of solution may be impracticable and heuristic methods must be used. Lower bounds for the frequency assignment problem can be used to assess the performance of these heuristic methods. In this paper, we present and assess a number of fewer bounds. Methods of reducing the size of the problem before application of the heuristic methods are also described.