Group for Research in Decision Analysis

G-99-04

The Height and Length of Colour Switching

and

Let G be a simple graph and C and D two proper colourings of G. The problem of colour switching consists of finding a sequence of vertex recolourings that transforms C into D, all intermediate colourings being proper. The height of a colour switching is the number of additional colours used (i.e., colours that are neither in C nor in D). The length of a colour switching is the number of vertex recolourings in the switching. We study the minimum height and the minimum length of colour switchings in various classes of graphs. This problem is a simplified model of frequency reassignment in mobile telecommunication systems.

, 13 pages

This cahier was revised in July 1999