Cop number partition of planar graphs

Classification of planar graphs by cop number · arXiv:1709.09050

arXiv Problem medium confidence— first stated 2018-04-22

Authors: Anthony Bonato, Bojan Mohar

Status open high confidence

The problem of classifying which connected planar graphs have cop number 1, 2, or 3 remains fully open as of 2026. Cop-win planar graphs (cop number 1) are precisely the dismantlable ones, and outerplanar graphs have cop number at most 2 with the chordal outerplanar ones being cop-win, but no complete structural characterisation of planar graphs with cop number 2 or 3 is known. Multiple recent surveys and follow-up papers confirm this is still an active open problem.

Reviewer notes. No follow-up paper resolving the full classification was found in up to 5 web searches. The 2024 paper arXiv:2409.16279 studies 1-planar graphs (a broader class) and does not resolve the planar classification. The toroidal result (arXiv:1904.07946, Lehner) is for toroidal graphs, not planar. The conjecture remains open with high confidence.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Classify which planar graphs have cop number $i$, for $1 \leq i \leq 3$.

Context

By Theorem 1, every connected planar graph has cop number 1, 2, or 3. Cop-win graphs are precisely the dismantlable ones, which may eventually aid in classifying planar cop-win graphs, but a complete classification for all three cop number values remains open.

Notes. PDF source; stated as open in survey prose

Source paper

Topological directions in Cops and Robbers
Anthony Bonato, Bojan Mohar · 2018-04-22
https://arxiv.org/abs/1709.09050 PDF source