Monday, April 5, 3pm ET (8pm BST, 7am Tue NZST)
Raphael Steiner, TU Berlin
Directed graphs: Substructures and Coloring

Abstract:

Two popular topics that are classically studied in graph theory are (A) substructures of “dense” graphs and (B) substructures of graphs with large chromatic number. Well-known notions of “substructure” used in this context are (induced) subgraphs, minors, and subdivisions. Unfortunately, interesting generalizations of these concepts to the directed setting, despite being very natural, have received considerably less attentation. In this talk, I want to popularize this topic by surveying some intriguing open problems and known partial results (some of my own) related to the following questions.

(A) Which substructures can be found in digraphs that are very dense? (Meaning that they have large minimum out- and/or in-degree).

(B) Which substructures can be found in digraphs whose dichromatic number is large? (Dichromatic number being an established extension of the chromatic number to directed graphs).