or the one-cop-moves game [17]. The corresponding cop number of a graph G in this game variant is called the one-cop-moves cop number of G, and is denoted by c 1 (G). The one-cop-moves cop number has been studied for various special families of graphs [2,12,3,15]. On the other hand, relatively little is known about the behaviour of the one-cop-moves cop number of connected planar graphs [5]. In particular, it is still open at present whether or not there exists an absolute constant k such that c 1 (G) ≤ k for all connected planar graphs G [3,17]. Instead of attacking this problem directly, one may try to establish lower bounds on sup{c 1 (G) : G is a connected planar graph} as a stepping stone. Note that the dodecahedron D is a connected planar graph with classical cop number equal to 3 [1]. Since any winning strategy for the robber on D in the classical cops-androbbers game can also be applied to D in the one-cop-moves game, it follows that c 1 (D) ≥ 3, and this immediately gives a lower bound of 3 on sup{c 1 (G) : G is a connected planar graph}. To the best of our knowledge, there has hitherto been no improvement on this lower bound. Sullivan, Townsend and Werzanski [15] recently asked whether or not sup{c 1 (G) : G is a connected planar graph} ≥ 4. The goal of the present work is to settle this question affirmatively: there is a connected planar graph whose one-cop-moves cop number is at least 4.
Theorem 1. There is a connected planar graph D such that c 1 (D) ≥ 4.
Due to space constraints, we shall only describe the construction of the planar graph D and very briefly outline a strategy for evading three cops on D.
The construction of D starts with a dodecahedron D. We will add straight line segments on the surface of D to partition each pentagonal face of D into small polygons. For each pentagonal face U of D, we add 48 nested nonintersecting closed pentagonal chains, which are called pentagonal layers, such that each side of a layer is parallel to the corresponding side of U . Each vertex of a layer is called a corner of that layer. For convenience, the innermost layer is also called the 1-st layer in U and the boundary of U is also called the outermost layer of U or the 49-th layer of U . We add a vertex o in the centre of U and connect it to each corner of U using a straight line segment which passes through the corresponding corners of the 48 inner layers. For each side of the n-th layer (1 ≤ n ≤ 49), we add 2n + 1 internal vertices to partition the side path into 2n + 2 edges of equal length. Add a path of length 2 from the centre vertex o to every vertex of the innermost layer to partition the region inside the 1-st layer into 20 pentagons. Further, for each pair of consecutive pentagonal layers, say the n-th layer and the (n + 1)-st layer (1 ≤ n ≤ 48), add paths of length 2 from vertices of the n-th layer to vertices of the (n + 1)-st layer such that the region between the two layers is partitioned into 5(2n + 2) hexagons and 10 pentagons as illustrated in Figure 1. Let D be the graph consisting of all vertices and edges current on the surface of the dodecahedron D (including all added vertices and edges). Since D is constructed on the surface of a dodecahedron without any edge-crossing, D must be a planar graph.
For n ∈ {1, . . . , 49}, L U ,n denotes the n-th pentagonal layer of a pentagonal face U , starting from the innermost layer. The pentagonal faces of D are denoted by U, U 1 , U 2 , . . . , U 10 , U 11 (see Figure 2).
Let γ denote the robber. In Algorithm 1, we give a high-level description of γ's winning strategy against three cops on D.
Algorithm 1: High-level strategy for γ Since there are 12 pentagonal faces but only 3 cops, Step 1 of Algorithm 1 can be readily achieved. Let U denote the pentagonal face whose centre o is currently occupied by γ. The precise winning strategy for γ in Step 3 will depend on the relative positions of the cops when exactly one cop is 1 edge away from γ. The details of this phase of γ's winning strategy can be described in three cases: (A) when three cops lie in U ; (B) when exactly one cop lies in U ; (C) when exactly two cops lie in U . These cases reflect three possible strategies for the cops: all three cops may try to encircle γ, or one cop may try to chase γ while the remaining two cops guard the neighbouring faces of U , or two cops may try to encircle γ while the remaining cop guards the neighbouring faces of U .
The present work established separation between the classical cops-and-robbers game and the one-cop-moves game on planar graphs by exhibiting a connected planar graph whose one-cop-moves cop number exceeds the largest possible classical cop number of connected planar graphs. We believe that this result represents an important first step towards understanding the behaviour of the one-cop-moves cop number of planar graphs. It is hoped, moreover, that some of the proof techniques used in this work could be applied more generally to the one-cop-moves game played on any planar graph.
This work did not prove any upper bound for the one-cop-moves cop number of D; nonetheless, we believe that 4 cops are sufficient for catching the robber on D. It should also be noted that the Planar Separator Theorem of Lipton and Tarjan [8] may be applied to show that the one-cop-moves cop number of every connected graph with n vertices is at most O( √ n) (the proof is essentially the same as that in the case of planar directed graphs; see [9, Theorem 4.1]). The question of whether or not there exists a constant k such that c 1 (G) ≤ k for all connected planar graphs G [17] remains open. It is tempting to conjecture that such an absolute constant does exist.