Main Menu







Printer friendly page

Krieger-Nelson Lecture

PENNY HAXELL, University of Waterloo
Independent transversals

Let G be graph whose vertex set is partitioned into classes. When does there exist a set S of vertices, consisting of one vertex from each class, such that no two vertices of S are joined by an edge of G? Such a set is called an independent transversal of G with respect to the given vertex partition. It turns out that many mathematical questions can be formulated by asking whether an independent transversal exists in a particular graph with a particular vertex partition.

We describe a number of different conditions that guarantee the existence of an independent transversal in a given vertex-partitioned graph. We also outline some applications of these results in various different contexts.


top of page
Copyright © Canadian Mathematical Society - Société mathématique du Canada.
Any comments or suggestions should be sent to - Commentaires ou suggestions envoyé à: