37 problems

Meyniel's conjecture.

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…

Let $G$ be a graph embeddable on an orientable surface of genus $g$, and let $c(G)$ denote its cop-number, the minimum number of cops required to capture a robber on $G$. Schroeder…

Let $\textsc{C\&R}(G,k)$ denote the decision problem of determining whether $k$ cops can capture a robber on an undirected graph $G$. EXPTIME is the class of decision problems solv…

Erde–Kang–Lehner–Mohar–Schmid 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\geq 1$ be an integer. For a graph $G$, let its longest-path length be the maximum number of vertices in a path in $G$, and let $c(G)$ denote its cop number. Linear lower-bou…

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.

Let $G$ be a graph, and let $c_{s,s}(G)$ denote the cop number in the game where both cops and robbers have speed $s$. For positive integers $s$ and $s'$ with $s<s'$, monotonicity…

A planar graph is a graph that can be drawn in the plane without edge crossings, and the cop number of a graph is the minimum number of cops needed to guarantee capture of a robber…

Let $G$ be a graph in the setting of the paper's cop-number upper bound, with minimum degree $\delta$ and order $n$. Extension conjecture. The same upper bound holds for graphs wit…

Let $G$ be a graph with girth at least $7$ and sufficiently large minimum degree $\delta$, and suppose it has at most $O(n^{1-\alpha})$ cycles of length at most $6$, where $n$ is i…

Let $G$ be a graph with minimum degree $\delta$ and girth $g$, and let $c(G)$ denote its cop number. A known lower bound is … Bradshaw–Hosseini–Mohar–Stacho conjecture. The exponen…

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

Meyniel's conjecture. The cop number of every connected $n$-vertex graph is $obreakformat{o}( obreakformat{ obreaktext{ obreak{sqrt}}{n}})$.

Bonato–Mohar conjecture. Bonato and Mohar conjectured that

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…

Kinnersley–Peterson conjecture. There exists an $n$-vertex graph $G$ such that

Let $GP(n,k)$ be a generalized Petersen graph, and let $c(GP(n,k))$ denote its cop number. The known graphs with cop number $2$ are those with $k=1$, together with those satisfying…

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.

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…