McGill University - School of Computer Science
Algorithms Seminar
Everybody is welcome.
|
DATE:
|
Wednesday, March 29th
|
|
TIME:
|
4:30 PM - 5:30 PM
|
|
PLACE:
|
McConnell 320
|
|
TITLE:
|
Graph imperfection
|
|
SPEAKER:
|
Colin McDiarmid, Oxford University
|
Given a graph G and a non-negative integer weight X_v for each node~v,
a {em weighted colouring} of the pair G,x is an assignment to each node~v
of a set of X_v colours such that adjacent vertices receive disjoint sets
of colours. We are interested in such colourings when the maximum weight X_v
is large, and in particular in the ratio of the ratio of the number of colours
needed to the clique-based lower bound. An application where this problem arises
is in the design of cellular communication systems, where we need to assign sets
of radio frequency channels (colours) to transmitters (nodes), using few channels
but avoiding excessive interference.
We shall introduce a relevant graph invariant,
the `imperfection ratio' imp(G), and present some investigations concerning it.
This invariant satisfies for example \: imp(G) \geq 1, imp(G)=1 if and only if
G is perfect, imp(G)=imp(\bar{G}), and if G is an imperfect line graph then
imp(G) = \frac{g}{g-1} where g is the minimum length of an odd hole. It is also
related for example to the graph entropy of G and bar{G}.
Much of this is joint work with Stefanie Gerke.
Direct questions, comments, additions to and removals from the mailing
list, and suggestions for speakers to us at
cgm-help@cgm.cs.mcgill.ca.