Hyperbolicity and chordality of a graph (Q540017): Difference between revisions

Summary: Let \(G\) be a connected graph with the usual shortest-path metric \(d\). The graph \(G\) is \(\delta\)-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\delta\). The graph \(G\) is \(k\)-chordal provided it has no induced cycle of length greater than \(k\). \textit{G. Brinkmann}, \textit{J. H. Koolen} and \textit{V. Moulton} [``On the hyperbolicity of chordal graphs,'' Ann. Comb. 5, No.\,1, 61--69 (2001; Zbl 0985.05021)] found that every 3-chordal graph is 1-hyperbolic and that graph is not \(\frac{1}{2}\)-hyperbolic if and only if it contains one of two special graphs as an isometric subgraph. For every \(k \geq 4\), we show that a \(k\)-chordal graph must be \(\frac{\lfloor\frac{k}{2}\rfloor}{2}\)-hyperbolic and there does exist a \(k\)-chordal graph which is not \(\frac{\lfloor \frac{k-2}{2} \rfloor}{2}\)-hyperbolic. Moreover, we prove that a 5-chordal graph is \(frac{1}{2}\)-hyperbolic if and only if it does not contain any of a list of five special graphs as an isometric subgraph.