Cops and robber on subclasses of \(P_5\)-free graphs

• Published in: arXiv.org 2022-11
• Main Authors: Gupta, Uttam K, Mishra, Suchismita, Pradhan, Dinabandhu
• Format: Article
• Language: English
• Subjects: Apexes; Diamonds; Games; Graph theory; Graphs
• ISSN: 2331-8422

The game of cops and robber is a turn based vertex pursuit game played on a connected 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_t\), \(H\))-free graph is at most \(t-3\), where \(H\) is a cycle of length at most \(t\) or a claw. So the conjecture of Sivaraman is true for (\(P_5\), \(H\))-free graphs, where \(H\) is a cycle of length at most \(5\) or a claw. 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\}\).