Tree-depth and vertex-minors

DOI10.1016/J.EJC.2016.03.001MaRDI QIDQ281932zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Graph minors (05C83)

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.

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

Cites work

• scientific article; zbMATH DE number 3156382 (Why is no real title available?)
• scientific article; zbMATH DE number 177438 (Why is no real title available?)
• Approximating clique-width and branch-width
• Graphs of small rank-width are pivot-minors of graphs of small tree-width
• Handle-rewriting hypergraph grammars
• Kernelizing MSO properties of trees of fixed height, and some consequences
• Principal pivot transforms: Properties and applications
• Rank-width and vertex-minors
• Tree-depth, subgraph coloring and homomorphism bounds
• 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

(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.
• scientific article; zbMATH DE number 7029306 (Why is no real title available?)

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)