Cop number of graphs without long holes

12/30/2019
by   Vaidy Sivaraman, et al.
0

A hole in a graph is an induced cycle of length at least 4. We give a simple winning strategy for t-3 cops to capture a robber in the game of cops and robbers played in a graph that does not contain a hole of length at least t. This strengthens a theorem of Joret-Kaminski-Theis, who proved that t-2 cops have a winning strategy in such graphs. As a consequence of our bound, we also give an inequality relating the cop number and the Dilworth number of a graph.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset