pith. sign in

arxiv: 1403.7024 · v1 · pith:6B2KS4P7new · submitted 2014-03-27 · 💻 cs.DM · math.CO

Tree-depth and Vertex-minors

classification 💻 cs.DM math.CO
keywords boundedgraphgraphsshrub-depthtree-depthvertex-minorseveryquestions
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.