Forbidden-subgraph classes of graphs with no long induced path are shown to have cop number at most about k/2 for (P_k,E)-free graphs and at most ceil(2p/3)+3 when the longest path has p vertices.
Cop number of $2K_2$-free graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We prove that the cop number of a $2K_2$-free graph is at most $2$ if it has diameter $3$ or does not have an induced cycle of length $k$, where $k \ \in \{3,4,5\}$. We conjecture that the cop number of every $2K_2$-free graph is at most $2$.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
ACCEPT 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Cops and Robbers on Graphs with Path Constraints
Forbidden-subgraph classes of graphs with no long induced path are shown to have cop number at most about k/2 for (P_k,E)-free graphs and at most ceil(2p/3)+3 when the longest path has p vertices.