The ACO Seminar (2017–2018)

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.