Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 18, 2008, 12:15 pm
Duration: This information is not available in the database
Location: CAB G51
Speaker: Robert Berke
A transversal T of a multipartite graph is a subset of the vertices such that each partite set contains exactly one vertex from T. An independent transversal is a transversal forming an independent set in the graph. In a series of work for every m,n the largest maximum degree d has been determined such that every m-partite graph with maximum degree at most d and partite sets containing at least n vertices each is guaranteed to contain an independent transversal. We started to investigate the corresponding maximum degree for matching transversals - transversals that induce isolated vertices and isolated edges in the graph - and determine its value for 3-partite graphs and find lower and upper bounds for the 4-partite case.
Joint work with Penny Haxell and Tibor Szabó.
Automatic MiSe System Software Version 1.4803M | admin login