@. Otherwise, By the induction hypothesis, this implies that (y (c,r) , v i ) was also marked Ifr) })?X i+1 and since (c, r) is marked with label ?+1 by the marking procedure in X i+1 , then (y (c,r) , y) must be marked by Mark(X i+1 ) with label at most ?. By the induction hypothesis, this implies that (y (c,r) , y) has been marked by Mark(X i ). Hence, it remains to show that y ? N k (r, G \ {x (c,r) , y (c,r) }) ? X i+1 . Let P be a path of length at most k between r and v i in G \ {x (c,r) , y (c,r) }. If x or y belongs to P, then we trivially get that y ? N k (r, G\{x (c,r) , y (c,r) })?X i+1, Otherwise, this means that r ? N k (v i , G \ {x, y}) ? X i and r ? N 1 (y) holds by definition of the bidismantling order. Hence, y ? N k (r, G \ {x (c,r) , y (c,r) }) ? X i+1 . References

R. P. Anstee and M. Farber, On bridged graphs and cop-win graphs, Journal of Combinatorial Theory, Series B, vol.44, issue.1, pp.22-28, 1988.
DOI : 10.1016/0095-8956(88)90093-7
URL : http://doi.org/10.1016/0095-8956(88)90093-7

M. Aigner and M. Fromme, A game of cops and robbers, Discrete Applied Mathematics, vol.8, issue.1, pp.1-12, 1984.
DOI : 10.1016/0166-218X(84)90073-8

B. Alspach, Searching and sweeping graphs: a brief survey, Le Matematiche, vol.59, pp.5-37, 2004.

T. Andreae, On a pursuit game played on graphs for which a minor is excluded, Journal of Combinatorial Theory, Series B, vol.41, issue.1, pp.37-47, 1986.
DOI : 10.1016/0095-8956(86)90026-2

H. Bandelt and V. Chepoi, A Helly theorem in weakly modular space, Discrete Mathematics, vol.160, issue.1-3, pp.25-39, 1996.
DOI : 10.1016/0012-365X(95)00217-K

H. Bandelt and V. Chepoi, Metric graph theory and geometry: a survey, Surveys on Discrete and Computational Geometry. Twenty Years later, pp.49-86, 2008.
DOI : 10.1090/conm/453/08795
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.81.2429

H. Bandelt, M. Farber, and P. Hell, Absolute reflexive retracts and absolute bipartite retracts, Discrete Applied Mathematics, vol.44, issue.1-3, pp.9-20, 1993.
DOI : 10.1016/0166-218X(93)90219-E
URL : http://doi.org/10.1016/0166-218x(93)90219-e

I. Benjamini, Survival of the weak in hyperbolic spaces, a remark on competition and geometry, Proc. Amer, pp.723-726, 2002.

A. Berarducci and B. Intrigila, On the Cop Number of a Graph, Advances in Applied Mathematics, vol.14, issue.4, pp.389-403, 1993.
DOI : 10.1006/aama.1993.1019

C. Berge, Hypergraphs: Combinatorics of Finite Sets, 1989.

A. Bonato and E. Chiniforooshan, Pursuit and evasion from a distance: algorithms and bounds, Proceedings of ANALCO'09
DOI : 10.1137/1.9781611972993.1
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.8002

A. Brandstädt, F. F. Dragan, V. Chepoi, and V. I. Voloshin, Dually Chordal Graphs, SIAM Journal on Discrete Mathematics, vol.11, issue.3, pp.437-455, 1998.
DOI : 10.1137/S0895480193253415

G. R. Brightwell and P. Winkler, Gibbs Measures and Dismantlable Graphs, Journal of Combinatorial Theory, Series B, vol.78, issue.1, pp.415-435, 1999.
DOI : 10.1006/jctb.1999.1935
URL : http://doi.org/10.1006/jctb.1999.1935

V. Chepoi, Graphs of Some CAT(0) Complexes, Advances in Applied Mathematics, vol.24, issue.2, pp.125-179, 2000.
DOI : 10.1006/aama.1999.0677
URL : http://doi.org/10.1006/aama.1999.0677

V. Chepoi, F. Dragan, B. Estellon, M. Habib, and Y. Vaxès, Notes on diameters, centers, and approximating trees of ??-hyperbolic geodesic spaces and graphs, Symposium on Computational Geometry, pp.59-68, 2008.
DOI : 10.1016/j.endm.2008.06.046

E. Chiniforooshan, A better bound for the cop number of general graphs, Journal of Graph Theory, vol.38, issue.1, pp.45-48, 2008.
DOI : 10.1002/jgt.20291

N. E. Clarke, A witness version of the Cops and Robber game, Discrete Mathematics, vol.309, issue.10, pp.3292-3298, 2009.
DOI : 10.1016/j.disc.2008.09.032

F. V. Fomin, P. Golovach, and J. Kratochvíl, On tractability of Cops and Robbers game, 5th Ifip International Conference On Theoretical Computer Science, pp.171-185, 2008.
DOI : 10.1007/978-0-387-09680-3_12

F. V. Fomin, P. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan, Pursuing a fast robber on a graph, Theoretical Computer Science, vol.411, issue.7-9
DOI : 10.1016/j.tcs.2009.12.010
URL : https://hal.archives-ouvertes.fr/inria-00476686

F. V. Fomin and D. Thilikos, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science, vol.399, issue.3, pp.236-245, 2008.
DOI : 10.1016/j.tcs.2008.02.040
URL : http://doi.org/10.1016/j.tcs.2008.02.040

M. Gromov, Hyperbolic Groups, MSRI Series, pp.75-263, 1987.
DOI : 10.1007/978-1-4613-9586-7_3

F. Haglund, Complexes simpliciaux hyperboliques de grande dimension, Prepublication Orsay, vol.71, p.32, 2003.

P. Hell and J. Ne?et?il, Graphs and Homomorphisms, 2004.
DOI : 10.1093/acprof:oso/9780198528173.001.0001

T. Januszkiewicz and J. Swiatkowski, Simplicial nonpositive curvature, Publications math??matiques de l'IH??S, vol.104, issue.1, pp.1-85, 2006.
DOI : 10.1007/s10240-006-0038-5
URL : http://archive.numdam.org/article/PMIHES_2006__104__1_0.pdf

V. Isler, S. Kannan, and S. Khanna, Randomized Pursuit-Evasion with Local Visibility, SIAM Journal on Discrete Mathematics, vol.20, issue.1, pp.26-41, 2006.
DOI : 10.1137/S0895480104442169
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.3455

R. Küsters, Memoryless Determinacy of Parity Games, Automata, Logics, and Infinite Games: A Guide to Current Research, pp.95-106, 2002.
DOI : 10.1007/3-540-36387-4_6

N. Nisse and K. Suchan, Fast Robber in Planar Graphs, Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp.312-323, 2008.
DOI : 10.1016/0095-8956(85)90093-0
URL : https://hal.archives-ouvertes.fr/inria-00423451

R. J. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Discrete Mathematics, vol.43, issue.2-3, pp.235-239, 1983.
DOI : 10.1016/0012-365X(83)90160-7

A. Quilliot, Probì emes de jeux, de point fixe, de connectivité et de représentation sur des graphes, des ensembles ordonnés et des hypergraphes, Thèse de doctorat d'´ etat, 1983.

A. Quilliot, A short note about pursuit games played on a graph with a given genus, Journal of Combinatorial Theory, Series B, vol.38, issue.1, pp.89-92, 1985.
DOI : 10.1016/0095-8956(85)90093-0

B. S. Schröder, The copnumber of a graph is

D. O. Theis, The cops and robber game on series-parallel graphs, 2008.