Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, December 10, 2002 - 4:30pm

Penny Haxell

Bell Labs

Location

University of Pennsylvania

DRL 4N30

let G be a graph whose vertex set is partitioned into classes V1,...,Vt. An independent transversal of G with respect to the given classes is an independent set v1,...,vt in G such that vi is in Vi for each i. We give conditions that guarantee the existence of an independent transversal in a graph with specified vertex classes, and we show how various colouring and matching problems can be addressed using these results.