





















The game of cops and robber has been studied for many years. Denoting $\mathsf{Forb}(4K_1)$ to be the family of all graphs that contain no induced subgraph isomorphic to $4K_1$ (e.g., with independence number less than $4$), we prove that for any $G\in\mathsf{Forb}(4K_1)$, we have $c(G)\leq 2$, where $c(\cdot)$ is the cop number. This improves a lower bound of a question proposed by Char et al. in a recent paper (arxiv, 2025), that any counterexample of a conjecture raised by Turcotte (2022) when $p=4$ must have at least 14 vertices.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。