Cops-and-robber games on digraphs

János Barát

October 13, 2000

Abstract

The proof of the celebrated Graph Minor Theorem of Robertson and Seymour has a central concept called tree-width. This is a number associated to a graph, which shows the tree-likeness of the graph in the following sense. The tree-width of G is at most k − 1 iff we can ’hide’ G in a help-tree, when the vertices of the tree are allowed to be blown up to graphs of size at most k. The important fact is that this is a minor-monotone graph parameter. A variation of this is called path-width, when the help-tree is restricted to be a path.

Beside the original definitions, there are some equivalent formulations of these numbers. One of them is especially nice. It comes from ’cops-and-robber’ games on graphs. Tree-width corresponds to the visible robber case, and path-width to the invisible one. We show some basic properties of these games to get everybody acquainted with the concepts.

Recently a lot of attempts were done to generalize the above notions to directed graphs. Our approach is from the cops-and-robber games point of view. We also consider a directed version of path-width first suggested by Reed, Seymour and Thomas. We prove its equivalence to a number arising from a cops-and-robber game on digraphs. Moreover we prove that k cops can capture an invisible robber if and only if they can do it in a nice monotone way. The methods are based on two related articles about undirected graphs written by Bienstock and Seymour resp. Bienstock, Robertson, Seymour and Thomas.

We also mention some open problems in connection with our work. email: jbarat@math.u-szeged.hu