{
  "id": "1908.11478",
  "version": "v1",
  "published": "2019-08-29T23:10:24.000Z",
  "updated": "2019-08-29T23:10:24.000Z",
  "title": "The Cop Number of Graphs with Forbidden Induced Subgraphs",
  "authors": [
    "Mingrui Liu"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In the game of Cops and Robber, a team of cops attempts to capture a robber on a graph $G$. Initially, all cops occupy some vertices in $G$ and the robber occupies another vertex. In each round, a cop can move to one of its neighbors or stay idle, after which the robber does the same. The robber is caught by a cop if the cop lands on the same vertex which is currently occupied by the robber. The minimum number of cops needed to guarantee capture of a robber on $G$ is called the {\\em cop number} of $G$, denoted by $c(G)$. We say a family $\\cal F$ of graphs is {\\em cop-bounded} if there is a constant $M$ so that $c(G)\\leq M$ for every graph $G\\in \\cal F$. Joret, Kamin\\'nski, and Theis [Contrib. Discrete Math. 2010] proved that the class of all graphs not containing a graph $H$ as an induced subgraph is cop-bounded if and only if $H$ is a linear forest; morerover, $C(G)\\leq k-2$ if if $G$ is induced-$P_k$-free for $k\\geq 3$. In this paper, we consider the cop number of a family of graphs forbidding certain two graphs and generalized some previous results.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-08-29T23:10:24.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C57"
    ],
    "keywords": [
      "cop number",
      "forbidden induced subgraphs",
      "linear forest",
      "cops occupy",
      "robber occupies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}