{
  "id": "1906.05753",
  "version": "v1",
  "published": "2019-06-13T15:30:53.000Z",
  "updated": "2019-06-13T15:30:53.000Z",
  "title": "Graphs of bounded depth-$2$ rank-brittleness",
  "authors": [
    "O-joung Kwon",
    "Sang-il Oum"
  ],
  "comment": "20 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "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. This allows us to prove that for every positive integer $n$, graphs with no vertex-minor isomorphic to the disjoint union of $n$ copies of $P_5$ have bounded rank-depth and bounded linear rank-width.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-06-13T15:30:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "disjoint union",
      "subdivision",
      "bounded linear rank-width",
      "vertex-minor isomorphic",
      "internal node"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}