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