Obstructions for bounded shrub-depth and rank-depth
arXiv:1911.00230 · doi:10.1016/j.jctb.2021.01.005
Abstract
Shrub-depth and rank-depth 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 an analogous statement for shrub-depth and rank-depth, which was conjectured by Hliněný, Kwon, Obdržálek, and Ordyniak [Tree-depth and vertex-minors, European J.~Combin. 2016]. Namely, 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 , the class of graphs with no vertex-minor isomorphic to the path on vertices has bounded shrub-depth.
arXiv comment19 pages, 5 figures; accepted to Journal of Combinatorial Theory Ser. B
References in corpus (9)
- Rank-width: Algorithmic and structural results
- On Low Tree-Depth Decompositions
- The grid theorem for vertex-minors
- Branch-depth: Generalizing tree-depth of graphs
- Graphs of Small Rank-width are Pivot-minors of Graphs of Small Tree-width
- Unavoidable vertex-minors in large prime graphs
- Classes of graphs with no long cycle as a vertex-minor are polynomially -bounded
- Scattered classes of graphs
- Graphs of bounded depth- rank-brittleness