BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: An independent transversal (IT) in a vertex-partitioned graph 
 G is an independent set in G consisting of one vertex in each partition cla
 ss. There are several known criteria that guarantee the existence of an IT\
 , of the following general form: the graph G has an IT unless the subgraph 
 GS of G\, induced by the union of some subset S of vertex classes\, has a s
 mall dominating set. These criteria have been used over the years to solve 
 many combinatorial problems. The known proofs of these IT theorems do not g
 ive efficient algorithms for actually finding an IT or a subset S of classe
 s such that GS has a small dominating set. Here we present appropriate weak
 enings of such results that do have effective proofs. These result in algor
 ithmic versions of many of the original applications of IT theorems. We wil
 l discuss a few of these here\, including hitting sets for maximum cliques\
 , circular edge colouring of bridgeless cubic graphs\, and hypergraph match
 ing problems. 
DTSTAMP:20190110T154600
DTSTART:20190114T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9 
 \n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Penny Haxell (University of Waterloo): Algorithms for independent t
 ransversals vs. small dominating sets
UID:95415874@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20190114-L-Hax
 ell.html
END:VEVENT
END:VCALENDAR