Tightness of 3-cop capture time bound for planar graphs

Tightness of linear capture time bound for planar graphs · arXiv:1709.09050

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

Authors: Anthony Bonato, Bojan Mohar

Status open high confidence

The conjecture from Bonato and Mohar (arXiv:1709.09050) asks whether the bound capt_3(G) ≤ 2n for planar graphs of order n is tight and, more specifically, whether any planar graph exists with capture time exceeding n. No follow-up paper resolving either question was found in the indexed literature as of May 2026. The most related general result — showing O(n^{k+1}) is asymptotically tight for k ≥ 2 cops in arbitrary graphs (Brandt et al., 2020) — does not apply to the planar setting with k = 3.

Reviewer notes. No follow-up found. The Brandt-Emek-Uitto-Wattenhofer paper (Theoretical Computer Science, 2020; doi:10.1016/j.tcs.2020.07.016) shows O(n^{k+1}) capture-time is tight for k ≥ 2 cops in general graphs, but this does not address the planar restriction. The paper arXiv:2406.01068 (2024) studies guarding isometric subgraphs and proves c_2(G) ≤ 3 for planar graphs (cop-move number variant), which is unrelated to the capt_3 tightness question. The conjecture remains open.

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

Problem. Is the bound $\mathrm{capt}_3(G) \leq 2n$ tight for planar graphs of order $n$? Does there exist a planar graph $G$ of order $n$ with $\mathrm{capt}(G) > n$?

Context

Theorem 5 establishes $\mathrm{capt}_3(G) \leq 2n$ for planar graphs of order $n$, improving the earlier $O(n^2)$ bound of Theorem 4. Whether this linear bound is tight is unknown; even finding a single planar graph with capture time exceeding $n$ remains open.

Notes. PDF source

Source paper

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