ACO The ACO Seminar (2017–2018)

Nov. 2, 3:30pm, Wean 8220
Penny Haxell, Waterloo
Stability and algorithms for independent transversals


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 (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 (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.

Back to the ACO home page