Nov. 2, 3:30pm, Wean 8220

Penny Haxell, Waterloo

Stability and algorithms for independent transversals

Penny Haxell, Waterloo

Stability and algorithms for independent transversals

Abstract:

An *independent transversal* (IT) in a vertex-partitioned graph
*G* is an independent set in *G* consisting of one vertex in each
partition class. This is a very basic notion that comes up in many
combinatorial problems. There are various criteria that guarantee the
existence of an IT in a given graph *G*. For example, if each
partition class has size at least *2Δ*(*G*) then *G* has an IT.

We consider *stability* questions for independent transversals,
and show in particular that if each partition class of *G* has size
close to *2Δ*(*G*) but *G* does not have an independent
transversal, then it contains an induced subgraph with a very special
structure.

The known proofs of the criteria mentioned above do not give efficient
*algorithms* for actually finding an IT. Here we also discuss appropriate weakenings of
such results that do have effective proofs.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.