19 problems

Erde–Kang–Lehner–Mohar–Schmid conjecture.

Meyniel's conjecture.

Let $P_k$ denote the path on $k$ vertices, let $\operatorname{claw}=K_{1,3}$, and let $c(G)$ denote the cop number of a graph $G$. A graph is $(P_k,\operatorname{claw})$-free if it…

Let $P_k$ denote the path on $k$ vertices, let $G$ be a graph, and let $c(G)$ denote its cop number. A graph is $P_k$-free if it contains no induced subgraph isomorphic to $P_k$. S…

For an integer $\ell\geq 3$, let $C_\ell$ be the cycle with $\ell$ vertices. A graph $G$ is $C_\ell$-free if it contains no induced subgraph isomorphic to $C_\ell$; write $c(G)$ fo…

Two 1-visibility cops cleaning conjecture. Two 1-visibility cops can clean at least $10$ vertices of $G$, or they can clean the whole graph.

Multi-layer analogue of Meyniel's conjecture. For every fixed $\tau\geqslant 1$ and every connected $n$-vertex graph $G$, one has

Let $G$ be a graph on $n$ vertices, and let $\pi^{\sf c}(G)$ denote its cop-pebbling number. Cop-pebbling bound conjecture. Every graph $G$ on $n$ vertices satisfies … This conject…

Let $G$ be a connected graph, and let $P_t$ denote the path on $t$ vertices. A graph is $P_t$-free if it has no induced subgraph isomorphic to $P_t$, and $c(G)$ denotes its cop num…

Cop-number conjecture. The graph $G$ can be won by $t-4$ cops.

Let $G$ be a graph of order $n$, and let $c(G)$ denote its cop number. Weak Meyniel's conjecture. There exists an $\varepsilon>0$ such that … This weaker form of Meyniel's conjectu…

Schröder's conjecture. For every $g\in\mathbb{N}$, we have

For each positive integer $n$, let $mc(n)$ and $mt(n)$ denote, respectively, the maximum cop number and maximum cop throttling number over all connected graphs of order $n$. The un…

Cop-number conjecture. The robber can be captured by $t-3$ cops.

Let $G$ be an $n$-vertex graph. Write $c_b(G)$ for its bridge-burning cop number and $\mathrm{capt}_b(G)$ for its bridge-burning capture time. Cubic-order conjecture. There exists…

Fast-robber grid conjecture. For all sufficiently large $R\in\mathbb{N}$,

Let $G$ be a graph. Write $\xi(G)$ for its containability number, the minimum number of cops needed to contain the robber, $c(G)$ for its cop number in the original Cops and Robber…

Restricted cop-number trap conjecture. If $H$ is an $s$-trap in $G$, then

Square-root bound conjecture. One should have