[Facets-of-complexity] Invitation & Link to Monday Lecture & Colloquium - July 12th 2021

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our last Monday Lecture & Colloquium in summer term, on July 12th at 14:15 h & 16:00 h, online via Zoom.

Invitation link:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

Online via:
Zoom - Invitation

Time: Monday, July 12th - 14:15 h

Lecture: Frédéric Havet (INRIA Sophia-Antipolis)

Title: Unavoidability and universality of digraphs

Abstract:

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 n_F such that F is n_F-unavoidable (resp. n_F-universal) if and only if F is acyclic, (resp. an oriented forest). However, determining the smallest n_F 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.

Break!

Time: Monday, July 12th - 16:00 h s.t.

Colloquium: Raphael Steiner (Technische Universität Berlin)

Title: The dichromatic number-a survey

Abstract:

The dichromatic number of a digraph is the smallest number of acyclic subsets of vertices (not spanning a directed cycle) that can be used to cover its vertex-set. This parameter is a natural extension of the chromatic number to directed graphs and has been introduced in 1980 by Erdös and Neumann-Lara. Since 2000, many groups of authors have studied this parameter intensively and in various settings. In this talk, I will give a small survey of this topic, which has concerned me quite a bit in the last 3-epsilon years. I will also mention own results obtained during my PhD at appropriate places.