Conférence Krieger-Nelson


PENNY HAXELL, University of Waterloo
Independent transversals
[PDF]

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.