Hyperbolicity and Chordality of a Graph - Wu, Yaokun; Zhang, Chengpeng (The Electronic Journal of Combinatorics, 2011)
Let G be a connected graph with the usual shortest-path metric d. The graph G is δ-hyperbolic provided for any vertices x,y,u,v in it, the two larger of the three sums d(u,v)+d(x,y),d(u,x)+d(v,y) and d(u,y)+d(v,x) differ by at most 2δ. The graph G is k-chordal provided it has no induced cycle of length greater than k. Brinkmann, Koolen and Moulton find that every 3-chordal graph is 1-hyperbolic and that graph is not 12-hyperbolic if and only if it contains one of two special graphs as an isometric subgraph. For every k≥ 4, we show that a k-chordal graph must be k2 floor2-hyperbolic and there does exist a k-chordal graph which is not k-22 floor2-hyperbolic. Moreover, we prove that a 5-chordal graph is 12-hyperbolic if and only if it does not contain any of a list of five special graphs as an isometric subgraph.