Research into the mathematics of radio channel assignment

Colin McDiarmid and Stefanie Gerke
University of Oxford

Graph colouring models can be used to study frequency assignment problems. Transmitters are then represented by nodes and frequencies by different colours. A graph's chromatic number is the number of colours which is necessary to colour the graph so that adjacent nodes receive disjoint colours. This is equivalent to the minimum number of frequencies which are needed to solve a frequency assignment problem.

In most cases it is hard to find or even to approximate the chromatic number of a graph. Stefanie Gerke's thesis relates the chromatic number, , to the clique number, , which is the size of the largest cluster of nodes (or transmitters), and so gives a lower bound on the number of colours (or frequencies) needed. The imperfection ratio imp is a limit of when the demand at some transmitter is large. The thesis demonstrates that a bound for the imperfection ratio can be found in many cases. This makes it possible to link the unknown quantity (the number of frequencies needed) to the known quantity (the largest cluster).

For further information on the project, please contact research@ra.gsi.gov.uk or Stefanie Gerke (Stefanie.Gerke@informatik.tu-muenchen.de).