{
  "id": "2001.00477",
  "version": "v1",
  "published": "2019-12-30T02:01:04.000Z",
  "updated": "2019-12-30T02:01:04.000Z",
  "title": "Cop number of graphs without long holes",
  "authors": [
    "Vaidy Sivaraman"
  ],
  "comment": "arXiv admin note: text overlap with arXiv:1903.01338",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "A hole in a graph is an induced cycle of length at least 4. We give a simple winning strategy for t-3 cops to capture a robber in the game of cops and robbers played in a graph that does not contain a hole of length at least t. This strengthens a theorem of Joret-Kaminski-Theis, who proved that t-2 cops have a winning strategy in such graphs. As a consequence of our bound, we also give an inequality relating the cop number and the Dilworth number of a graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-12-30T02:01:04.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "cop number",
      "long holes",
      "dilworth number",
      "simple winning strategy",
      "induced cycle"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}