2019/06/30 by O‐joung Kwon, O-joung Kwon, Sang-il Oum +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Bounded function #Brittleness #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Disjoint sets #Graph #Limits and Structures in Graph Theory #Mathematical analysis #Mathematics #Partition (number theory) #Physics #Rank (graph theory) #Subdivision #Vertex (graph theory) #math.CO
paper · pdf · doi:10.1002/jgt.22619
published as J. Graph Theory, 96:361-378, March 2021 · 23 pages, 4 figures
arxiv created 2020/03/01 · openalex publication_date 2020/09/14 · arxiv updated 2021/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract We characterize classes of graphs closed under taking vertex‐minors and having no and no disjoint union of copies of the 1‐subdivision of for some . Our characterization is described in terms of a tree of radius 2 whose leaves are labeled by the vertices of a graph , and the width is measured by the maximum possible cut‐rank of a partition of 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 . We prove that for all , every graph with sufficiently large depth‐2 rank‐brittleness contains or disjoint union of copies of the 1‐subdivision of as a vertex‐minor.