- This event has passed.
Ken-ichi Kawarabayashi (河原林 健一), Toward Directed Graph Minor Theory
Thursday, January 20, 2022 @ 4:30 PM - 5:30 PM KST
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.