Unavoidable pivot-minors in graphs of large rank-depth

2025/07/17 by Jungho Ahn, Kevin Hendrey, Ahn, Jungho +7 · 1 voice
Computer Science · Engineering · Mathematics · #05C50 #05C75 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.2507.12697

openalex publication_date 2025/07/17 · arxiv published 2025/07/17 · arxiv updated 2025/07/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

Shrub-depth and rank-depth are related graph parameters that are dense analogs of tree-depth. We prove that for every positive integer t, every graph of sufficiently large rank-depth contains a pivot-minor isomorphic to a path on t vertices or a graph consisting of two disjoint cliques of size t joined by a half graph. This answers an open problem raised by Kwon, McCarty, Oum, and Wollan in 2021.

Citations

• Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
• Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
• Tree-depth and Vertex-minors

Discussions

• #New_accepted_paper Jungho Ahn, Kevin Hendrey, *O-joung Kwon*, and *Sang-il Oum*, Unavoidable pivot-minors in graphs of large rank-depth, SIAM J. Discrete Math., accepted, 2026. arxiv.org/abs/2507.126 [bsky, 1 points, 0 comments]

Related

• Tree-depth and Vertex-minors
• Computing pivot-minors
• The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two
• Minors of two-connected graphs of large path-width
• Pivot-minors and the Erdős-Hajnal conjecture