{
  "id": "1809.04278",
  "version": "v1",
  "published": "2018-09-12T07:04:53.000Z",
  "updated": "2018-09-12T07:04:53.000Z",
  "title": "Classes of graphs with no long cycle as a vertex-minor are polynomially $χ$-bounded",
  "authors": [
    "Ringi Kim",
    "O-joung Kwon",
    "Sang-il Oum",
    "Vaidy Sivaraman"
  ],
  "comment": "13 pages, 2 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A class $\\mathcal G$ of graphs is $\\chi$-bounded if there is a function $f$ such that for every graph $G\\in \\mathcal G$ and every induced subgraph $H$ of $G$, $\\chi(H)\\le f(\\omega(H))$. In addition, we say that $\\mathcal G$ is polynomially $\\chi$-bounded if $f$ can be taken as a polynomial function. We prove that for every integer $n\\ge3$, there exists a polynomial $f$ such that $\\chi(G)\\le f(\\omega(G))$ for all graphs with no vertex-minor isomorphic to the cycle graph $C_n$. To prove this, we show that if $\\mathcal G$ is polynomially $\\chi$-bounded, then so is the closure of $\\mathcal G$ under taking the $1$-join operation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-09-12T07:04:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "long cycle",
      "polynomial function",
      "vertex-minor isomorphic",
      "cycle graph",
      "join operation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}