Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(2–3), 235–239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 89–92, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of k‐chordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, k≥3. We prove that k−1 cops are always sufficient to capture a robber in k‐chordal graphs. This leads us to our main result, a new structural decomposition for a graph class including k‐chordal graphs. We present a polynomial‐time algorithm that, given a graph G and k≥3, either returns an induced cycle larger than k in G, or computes a tree‐decomposition of G, each bag of which contains a dominating path with at most k−1 vertices. This allows us to prove that any k‐chordal graph with maximum degree Δ has treewidth at most (k−1)(Δ−1)+2, improving the O(Δ(Δ−1)
k−3) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(1–3), 45–61, 1997. Moreover, any graph admitting such a tree‐decomposition has small hyperbolicity). As an application, for any n‐vertex graph admitting such a tree‐decomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klogΔ+logn) bits and achieving an additive stretch of O(klogΔ). As far as we know, this is the first routing scheme with O(klogΔ+logn)‐routing tables and small additive stretch for k‐chordal graphs.
