Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 12 min ago
PreprintarXiv licencearXiv

Cop number of Pk-free graphs without a claw or a fork

  • Uttam K. Gupta
  • Dinabandhu Pradhan
  • Rashmi Rekha Swain
Open at sourcePDFDOICite

Abstract

In 2019, Liu proved that the cop number of any (Pk, claw)-free graph is at most k−3. In 2026, Clow and Meger improved and generalized the result of Liu by showing that every connected (Pk, E)-free graph has cop number at most ⌈ (k−1)/2 ⌉ + 3, where the graph E is obtained by subdividing two edges of a claw. In this paper, we show that every (Pk, claw)-free graph G has cop number at most ⌈ (k−1)/2 ⌉. This improves the result of Clow and Meger on claw-free graphs. We further show that this bound can be improved to ⌈ k/3⌉, when G contains a hole of length at least k−1. We show that the cop number of any (Pk, fork)-free graph is at most ⌈ (2(k−1))/3 ⌉. This also improves the result of Clow and Meger on fork-free graphs for some values of k. We further show that every (P7, fork)-free graph has cop number at most $3$, and this bound is tight.

Related

  1. Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
    Huaibin Zhou, Xiumei Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Packing colourings of claw-free subcubic graphs
    Federico Romaniello
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A tris of perfect matchings in bridgeless claw-free cubic graphs
    Jean Paul Zerafa
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Claw-free perfect graphs are chromatic-choosable
    Suchismita Mishra, Narayanan Narayanan, Umesh Shankar
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Claw-Free and Line Graph Edge Deletion on Block Graphs
    Rajat Adak
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{gupta2026number,
  title = {{Cop number of $P_k$-free graphs without a claw or a fork}},
  author = {Uttam K. Gupta and Dinabandhu Pradhan and Rashmi Rekha Swain},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20129},
  eprint = {2610.20129},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20129},
}
RIS
TY  - UNPB
TI  - Cop number of P_k-free graphs without a claw or a fork
AU  - Uttam K. Gupta
AU  - Dinabandhu Pradhan
AU  - Rashmi Rekha Swain
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20129
UR  - https://arxiv.org/abs/2610.20129
AB  - In 2019, Liu proved that the cop number of any (P_k, claw)-free graph is at most k−3. In 2026, Clow and Meger improved and generalized the result of Liu by showing that every connected (P_k, E)-free graph has cop number at most ⌈ (k−1)/2 ⌉ + 3, where the graph E is obtained by subdividing two edges of a claw. In this paper, we show that every (P_k, claw)-free graph G has cop number at most ⌈ (k−1)/2 ⌉. This improves the result of Clow and Meger on claw-free graphs. We further show that this bound can be improved to ⌈ k/3⌉, when G contains a hole of length at least k−1. We show that the cop number of any (P_k, fork)-free graph is at most ⌈ (2(k−1))/3 ⌉. This also improves the result of Clow and Meger on fork-free graphs for some values of k. We further show that every (P_7, fork)-free graph has cop number at most $3$, and this bound is tight.
ER  -