기초과학연구원 이산수학그룹
On January 20, 2022, Ken-ichi Kawarabayashi from the National Institute of Informatics, Japan gave an online talk at the Virtual Discrete Math Colloquium on the recent progress towards the directed graph minor theory. The title of his talk was “Toward Directed Graph Minor Theory“.
Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. It also gives many exciting algorithmic consequences.
In this work, I would like to talk about our attempt to extend Graph minor project to directed graphs. Topics include
1. The directed grid theorem
2. The directed flat wall theorem
3. Tangle tree decomposition
4. Variant of the directed disjoint paths problems
5. Toward the structure (and decomposition) theorem for H-minor-free digraphs.
Joint work with Stephan Kreutzer, O-joung Kwon, Archontia Giannopoulou.