Bounding the cop-number of a graph in terms of its genus

Add to your list(s) Download to your calendar using vCal

• Florian Lehner (University of Warwick)
• Tuesday 30 January 2018, 15:00-16:00
• Watson LTA.

If you have a question about this talk, please contact Allan Lo.

The cop-and-robber game is a game on a graph played between two players, a set of cops, and a single robber. The rules of the game are as follows: In the first round both the cops and the robber choose starting vertices, in each consecutive even round each cop can move to a neighbouring vertex, in odd rounds, the robber can move to a neighbouring vertex. The game has perfect information, meaning that each player knows the positions of both the cops and the robber at any point in time. The cops win, if after some finite number of steps one of them occupies the same vertex as the robber, otherwise the robber wins.

A graph $G$ is called $k$-cop win, if for a set of $k$ cops there is a strategy to win the game no matter how the robber plays. The cop number $c(G)$ is the least number $k$ such that $G$ is $k$-cop win. This notion was first introduced in 1984 by Aigner and Fromme, who showed that the cop number of a planar graph is at most $3$. Using similar techniques, Quilliot showed that if $G$ can be embedded on an orientable surface of genus $g$, then $c(G) \leq 2g+3$. Schroeder subsequently improved this bound to $\frac 32g+3$ and conjectured an upper bound of $g+3$.

Using a reduction to a topological game played on an orientable surface, we are able to further improve the bound to $\frac 43 g + 3$ which to our knowledge is the first improvement since Schroeder first formulated his conjecture in 2001. (joint work with N. Bowler, J. Erde, and M. Pitz)

This talk is part of the Combinatorics and Probability seminar series.

This talk is included in these lists:

• Combinatorics and Probability seminar
• School of Mathematics events
• Watson LTA

Note that ex-directory lists are not shown.