Obstructions for bounded shrub-depth and rank-depth
From MaRDI portal
Publication:2033913
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 Hlinv{e}n'y, Kwon, Obdrv{z}'alek, 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.
Recommendations
Cites work
- Approximating clique-width and branch-width
- Branch-depth: generalizing tree-depth of graphs
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi\)-bounded
- Computing small pivot-minors
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Graph minors. X: Obstructions to tree-decomposition
- Graphs of bounded depth‐2 rank‐brittleness
- Graphs of small rank-width are pivot-minors of graphs of small tree-width
- scientific article; zbMATH DE number 15493 (Why is no real title available?)
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- Obstructions for linear rank-width at most 1
- On low tree-depth decompositions
- Rank-width and vertex-minors
- Scattered classes of graphs
- Structural sparsity
- Tree-depth and vertex-minors
- Tree-depth, subgraph coloring and homomorphism bounds
- Unavoidable vertex-minors in large prime graphs
- Upper bounds to the clique width of graphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
Cited in
(18)- Obstructions for linear rank-width at most 1
- Tree-depth and vertex-minors
- Obstructions for tree-depth
- When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
- Forbidden graphs for tree-depth
- Scattered classes of graphs
- Tree pivot-minors and linear rank-width
- Obstructions for bounded branch-depth in matroids
- Graphs of bounded depth‐2 rank‐brittleness
- Tight bound on treedepth in terms of pathwidth and longest path
- Vertex-minors of graphs: a survey
- Transducing paths in graph classes with unbounded shrubdepth
- Stable graphs of bounded twin-width
- Towards exact structural thresholds for parameterized complexity
- Shallow vertex minors, stability, and dependence
- Computing pivot-minors
- An overview of universal obstructions for graph parameters
- Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO
This page was built for publication: Obstructions for bounded shrub-depth and rank-depth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2033913)
