An Algorithmic Approach to Multicolouring
Professor Jeannette Janssen
Department of Mathematics and Statistics
Dalhousie University, Canada
Multicolouring is the assignment of sets of colours to the vertices of a graph, so that sets on adjacent vertices are disjoint. Weights on the vertices prescribe the cardinality of the colour sets. Multicolouring was first studied in the context of the polyhedral approach to graph colouring. The application of graph colouring to frequency assignment in cellular networks has given a new impulse to the study of multicolouring for its own sake.
While graph colouring is known to be hard in general, the situation can be different when we restrict ourselves to special classes of graphs. In the case of multicolouring, we can use the structure of the underlying graph to guide our algorithm. We will show a number of approximation algorithms with constant performance ratio for multicolouring on certain types of graphs. We focus on graphs derived from subgraphs of the triangular lattice, the so-called hexagon graphs, since such graphs arise naturally in the context of cellular networks. We will also discuss variations of the graph colouring problem that arise from the frequency assignment problem
The Big Sky Conference is sponsored by the National Science Foundation
and the Department of Mathematical Sciences.
Friday, 10 September 1999
4:10 p.m. in Continuing Education 203/204
Treats at 3:30 p.m. in the same
Colloquium home | Mathematical Sciences home | The University of Montana home