Springe direkt zu Inhalt

Lecture by Frédéric Havet (INRIA Sophia-Antipolis): Unavoidability and universality of digraphs

Jul 12, 2021 | 02:15 PM

A digraph F is n-unadoidable} (resp. n-universal) if it is contained in every tournament of order n (resp. n-chromatic digraph). Well-known theorems imply that there is an nF such that F is nF-unavoidable (resp. nF-universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest nF for which it occurs is a challenging question. In this talk, we survey the results on unavoidability and universality and detail some recent recults obtained with various co-authors.

Time & Location

Jul 12, 2021 | 02:15 PM


Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)