Ken-ichi Kawarabayashi (河原林 健一), 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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.