Seminar of Graph Theory - Tomáš Kaiser (22.4.2021)
Thursday 22.4.2021 at 9:50
Tomáš Kaiser (University of West Bohemia, Pilsen):
Independent transversals in graph
MS TEAMS code (users from Comenius University in Bratislava): gglxxc7
Link (guests outside Comenius University in Bratislava)
Abstract:
An independent transversal in a graph G with a given partition P of its vertex set is an independent set in G intersecting each block of P in a single vertex. Given a lower bound on the size of blocks of P, which conditions on the degrees in G imply the existence of an independent transversal? We will discuss topological and probabilistic aspects of this classical problem as well as recent developments related to the entropy compression method. Includes joint work with Carla Groenland, Matt Wales and Oscar Treffers.