COP AND ROBBER GAME AND HYPERBOLICITY.

In this note, we prove that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s' < s, are < δ-hyperbolic with δ = O(s²). We also show that the dependency between S and s is linear if s - s' = Ω(s) and G obeys a slightly stronger condition. This solves an open question from the paper [J. Chalopin et al., SIAM J. Discrete Math., 25 (2011), pp. 333-359]. Since any δ-hyperbolic graph is cop-win for s = 2r and s' = r + 2δ for any r > 0, this establishes a new--game-theoretical--characterization of Gromov hyperbolicity. We also show that for weakly modular graphs the dependency between δ and s is linear for any s' < s. Using these results, we describe a simple constant-factor approximation of the hyperbolicity δ of a graph on n vertices in O(n²) time when the graph is given by its distance matrix. [ABSTRACT FROM AUTHOR]