|国家预印本平台
首页|Unavoidable pivot-minors in graphs of large rank-depth

Unavoidable pivot-minors in graphs of large rank-depth

Unavoidable pivot-minors in graphs of large rank-depth

来源:Arxiv_logoArxiv
英文摘要

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.

Jungho Ahn、Kevin Hendrey、O-joung Kwon、Sang-il Oum

数学

Jungho Ahn,Kevin Hendrey,O-joung Kwon,Sang-il Oum.Unavoidable pivot-minors in graphs of large rank-depth[EB/OL].(2025-07-17)[2025-08-16].https://arxiv.org/abs/2507.12697.点此复制

评论