Groupe d’études et de recherche en analyse des décisions


The Height and Length of Colour Switching


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

Ce cahier a été révisé en juillet 1999