{
  "id": "1912.06957",
  "version": "v1",
  "published": "2019-12-15T01:42:53.000Z",
  "updated": "2019-12-15T01:42:53.000Z",
  "title": "Meyniel's conjecture on graphs of bounded degree",
  "authors": [
    "Seyyed Aliasghar Hosseini",
    "Bojan Mohar",
    "Sebastian Gonzalez Hermosillo de la Maza"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The game of Cops and Robbers is a well known pursuit-evasion game played on graphs. It has been proved \\cite{bounded_degree} that cubic graphs can have arbitrarily large cop number $c(G)$, but the known constructions show only that the set $\\{c(G) \\mid G \\text{ cubic}\\}$ is unbounded. In this paper we prove that there are arbitrarily large subcubic graphs $G$ whose cop number is at least $n^{1/2-o(1)}$ where $n=|V(G)|$. We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weak Meyniel's conjecture for all graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-12-15T01:42:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bounded degree",
      "weak meyniels conjecture",
      "arbitrarily large cop number",
      "arbitrarily large subcubic graphs",
      "pursuit-evasion game"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}