Tree-depth and vertex-minors

DOI10.1016/J.EJC.2016.03.001zbMATH Open1335.05168arXiv1403.7024OpenAlexW1827118975MaRDI QIDQ281932FDOQ281932

Authors: Petr Hliněný, Jan Obdržálek, Sebastian Ordyniak, O-joung Kwon 

Publication date: 11 May 2016

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: In a recent paper, Kwon and Oum claim that every graph of bounded rank-width is a pivot-minor of a graph of bounded tree-width (while the converse has been known true already before). We study the analogous questions for "depth" parameters of graphs, namely for the tree-depth and related new shrub-depth. We show that shrub-depth is monotone under taking vertex-minors, and that every graph class of bounded shrub-depth can be obtained via vertex-minors of graphs of bounded tree-depth. We also consider the same questions for bipartite graphs and pivot-minors.

Full work available at URL: https://arxiv.org/abs/1403.7024

Recommendations

• Obstructions for bounded shrub-depth and rank-depth
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Tree pivot-minors and linear rank-width
• Rank-width and vertex-minors
• Graphs of bounded depth‐2 rank‐brittleness

zbMATH Keywords

distance-hereditarylinear rank-widthpath-widthpivot-minorrank-widthtree-widthvertex-minor

Mathematics Subject Classification ID

Graph minors (05C83)

Cites Work

• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Tree-depth, subgraph coloring and homomorphism bounds
• Approximating clique-width and branch-width
• Principal pivot transforms: Properties and applications
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Rank-width and vertex-minors
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Kernelizing MSO properties of trees of fixed height, and some consequences
• Vertex-minors, monadic second-order logic, and a conjecture by Seese

Cited In (12)

• Tree pivot-minors and linear rank-width
• The vertex degrees of minimum spanning trees
• Minimum degree and minimum number of edge-disjoint trees
• Obstructions for bounded shrub-depth and rank-depth
• Branch-depth: generalizing tree-depth of graphs
• Treedepth Parameterized by Vertex Cover Number.
• Graphs of bounded depth‐2 rank‐brittleness
• Rank-width: algorithmic and structural results
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Vertex-minors of graphs: a survey
• Tree-width, clique-minors, and eigenvalues.
• Title not available (Why is that?)

This page was built for publication: Tree-depth and vertex-minors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281932)