Obstructions for bounded shrub-depth and rank-depth of graphs

Speaker: Sang-il Oum (KAIST/IBS)

Abstract: Shrub-depth and rank-depth of graphs are dense analogues of the tree-depth of a graph. It is well known that a graph has large tree-depth if and only if it has a long path as a subgraph. We prove that a graph has large rank-depth if and only if it has a vertex-minor isomorphic to a long path. This implies that for every integer t, the class of graphs with no vertex-minor isomorphic to the path on t vertices has bounded shrub-depth.

This is joint work with O-joung Kwon, Rose McCarty, and Paul Wollan.

Date and time: 5/11/2020 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p