Cops and Robbers, Clique Covers, and Induced Cycles

Abstract

We consider the Cops and Robbers game played on finite simple graphs. In a graph $G$, the number of cops required to capture a robber in the Cops and Robbers game is denoted by $c(G)$. For all graphs $G$, $c(G)\le \alpha (G)\le \theta (G)$ where $\alpha (G)$ and $\theta (G)$ are the independence number and clique cover number respectively. In 2022 Turcotte asked if $c(G)<\alpha (G)$ for all graphs with $\alpha (G)\ge 3$. Recently, Char, Maniya, and Pradhan proved this is false, at least when $\alpha =3$,by demonstrating the compliment of the Shrikhande graph has cop number and independence number $3$. We prove, using random graphs, the stronger result that for all $k\ge 1$ there exists a graph $G$ such that $c(G)=\alpha (G)=\theta (G)=k$. Next, we consider the structure of graphs with $c(G)=\theta (G)\ge 3$. We prove, using structural arguments, that any graphs $G$ which satisfies $c(G)=\theta (G)=k\ge 3$ contain induced cycles of all lengths $3\le t\le k+1$. This implies all perfect graphs $G$ with $\alpha (G)\ge 4$ have $c(G)<\alpha (G)$. Additionally,we discuss if typical triangle-free and $C_4$-free graphs will have $c(G)<\alpha (G)$.

15 pages, 1 figure