Cop number dichotomy for outerplanar graphs

Classification of outerplanar 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

Every outerplanar graph has cop number at most 2, and the four-cycle is the smallest outerplanar graph requiring 2 cops, but a complete characterization of which outerplanar graphs are 1-cop-win versus 2-cop-win remains open as of 2026. No follow-up paper resolving this classification was found in the searched literature.

Reviewer notes. Searches returned no paper providing a complete classification of outerplanar graphs by cop number. One hit (arXiv:2409.16279) addresses 1-planar graphs with bounded cop-number (a different graph class). Another (arXiv:2508.10443) treats the localization game on outerplanar graphs, not the standard cops-and-robbers classification. The AI-generated search summaries suggested 'outerplanar + chordal iff 1-cop-win' but this claim could not be attributed to any specific verified publication, so it is not cited here.

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

Problem. Classify which outerplanar graphs are $1$-cop-win and which are $2$-cop-win.

Context

By Theorem 3, every outerplanar graph has cop number at most 2. The smallest outerplanar graph with cop number 2 is the four cycle, but a full classification of outerplanar graphs by cop number 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