





















In 2019, Sivaraman conjectured that every $P_k$-free graph has cop number at most $k-3$. In the same year, Liu proved this conjecture for $(P_k,\text{claw})$-free graphs. Recently Chudnovsky, Norin, Seymour, and Turcotte proved this conjecture for $P_5$-free graphs. For $k\geq 6$ the conjecture remains widely opened. Let the $E$ graph be the $\text{claw}$ with two subdivided edges. We show that all $(P_k,E)$-free graphs have cop number at most $\lceil \frac{k-1}{2} \rceil +3$, which improves and generalizes Liu's result for $(P_k,\text{claw})$-free graphs. We also prove that if $G$ is a graph whose longest path is length $p$, then $G$ has cop number at most $\lceil \frac{2p}{3} \rceil+3$. This improves a bound of Joret, Kamiński, and Theis. Our proof relies on demonstrating that all $(P_k,\text{claw},\text{butterfly},C_4,C_5)$-free graphs have cop number at most $\lceil\frac{k-1}{3}\rceil +3$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。