Graphs of bounded depth-$2$ rank-brittleness

Abstract

We characterize classes of graphs closed under taking vertex-minors and having no $P_n$ and no disjoint union of $n$ copies of the $1$-subdivision of $K_{1,n}$ for some $n$. Our characterization is described in terms of a tree of radius $2$ whose leaves are labelled by the vertices of a graph $G$, and the width is measured by the maximum possible cut-rank of a partition of $V(G)$ induced by splitting an internal node of the tree to make two components. The minimum width possible is called the depth-$2$ rank-brittleness of $G$. We prove that for all $n$, every graph with sufficiently large depth-$2$ rank-brittleness contains $P_n$ or disjoint union of $n$ copies of the $1$-subdivision of $K_{1,n}$ as a vertex-minor.

arXiv comment23 pages, 4 figures

References in corpus (7)

• Rank-width: Algorithmic and structural results
• Excluded vertex-minors for graphs of linear rank-width at most k
• Branch-depth: Generalizing tree-depth of graphs
• Obstructions for bounded shrub-depth and rank-depth
• Unavoidable vertex-minors in large prime graphs
• Classes of graphs with no long cycle as a vertex-minor are polynomially $\chi$-bounded
• Scattered classes of graphs

Cited by in corpus (1)

• Obstructions for bounded shrub-depth and rank-depth