Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, June 14, 2018, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Rajko Nenadov
The Hajnal-Szemerédi theorem states that every graph G with n vertices and minimum degree at least (r-1)n/r contains a K_r-factor, that is a collection of disjoint copies of the complete graph on r vertices which together cover all the vertices of G, assuming r divides n. The bound on the minimum degree is easily seen to be optimal: take a complete r-partite graph in which one vertex class is of size n/r -1, one n/r + 1 and all other of size n/r. Such a graph has minimum degree (r-1)n/r - 1 and clearly does not contain K_r-factor. One particular feature of this example is that it contains a very large independent set. What happens if we exclude graphs with this property? Does a weaker bound on the minimum degree imply a K_r-factor if we additionally assume that G has sublinear independence number? In this talk I will give an overview of known results, present some new ones and discuss further research directions. Based on a joint work with Yanitsa Pehova (University of Warwick).
Automatic MiSe System Software Version 1.4803M | admin login