Tree-depth and Vertex-minors

2014/03/27 by Petr Hliněný, O-joung Kwon, Hliněný, Petr +5 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1403.7024

arxiv created 2014/03/27 · arxiv updated 2014/03/28

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.

Cited by

• Unavoidable pivot-minors in graphs of large rank-depth

Related

• Unavoidable pivot-minors in graphs of large rank-depth
• The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two
• Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
• Computing pivot-minors
• K₆ minors in 6-connected graphs of bounded tree-width