{
  "id": "2111.06079",
  "version": "v1",
  "published": "2021-11-11T07:20:44.000Z",
  "updated": "2021-11-11T07:20:44.000Z",
  "title": "Cops and robber on subclasses of $P_5$-free graphs",
  "authors": [
    "Uttam K. Gupta",
    "Suchismita Mishra",
    "Dinabandhu Pradhan"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "The game of cops and robber is a turn based vertex pursuit game played on a graph between a team of cops and a single robber. The cops and the robber move alternately along the edges of the graph. We say the team of cops win the game if a cop and the robber are at the same vertex of the graph. The minimum number of cops required to win in each component of a graph is called the cop number of the graph. Sivaraman [Discrete Math. 342(2019), pp. 2306-2307] conjectured that for every $t\\geq 5$, the cop number of a connected $P_t$-free graph is at most $t-3$, where $P_t$ denotes a path on $t$-vertices. Turcotte [Discrete Math. 345 (2022), pp. 112660] showed that the cop number of any $2K_2$-free graph is at most $2$, which was earlier conjectured by Sivaraman and Testa. Note that if a connected graph is $2K_2$-free, then it is also $P_5$-free. Liu showed that the cop number of a connected ($P_5$, claw)-free graph is at most $2$ that is the conjecture of Sivaraman is true for ($P_5$, claw)-free graphs. In this paper, we show that the cop number of a connected ($P_5,H$)-free graph is at most $2$, where $H\\in \\{C_4$, $C_5$, diamond, paw, $K_4$, $2K_1\\cup K_2$, $K_3\\cup K_1$, $P_3\\cup P_1\\}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-11-11T07:20:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "free graph",
      "cop number",
      "subclasses",
      "discrete math",
      "vertex pursuit game"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}