The Cops and Robber game on graphs with forbidden subgraphs or induced subgraphs
by
Dirk Oliver Theis
Université Libre de Bruxelles, Brussels, Belgium
Coauthors: Gwenaël Joret (Université Libre de Bruxelles, Brussels, Belgium) Marcin Kaminski (Université Libre de Bruxelles, Brussels, Belgium)

The Cops and Robber game is a two-player game with complete information played on undirected finite graphs. k cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if, after a move, a cop and the robber are on the same vertex. For a fixed finite graph, the minimum over all numbers k such that the cop player has a winning strategy is called the cop number of the graph.

Andreae (JCTB, 1986) showed that any class of graphs defined by forbidding a fixed graph as a minor has bounded cop number.

In this talk, we discuss the question whether classes of graphs defined by forbidding one or more graphs as either subgraphs or induced subgraphs have bounded cop number. In the case of a single forbidden graph, for both relations, we completely characterize the graphs which force the cop number to be bounded.

Date received: March 27, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cawn-19.