On the hyperbolicity of chordal graphs (Q5939209): Difference between revisions

The hyperbolicity of a metric space is the infimum of all \(\delta\) for which \(d(x,y)+ d(u,v)\leq \max\{d(x, u)+ d(y,v), d(x,v)+ d(y,u)\}+ \delta\) for all elements \(x\), \(y\), \(u\), \(v\) from the space. The notion can be viewed as expressing how `tree like' the space is, as spaces with hyperbolicity \(0\) are precisely the metric trees. This paper considers the hyperbolicity of graphs, with \(d\) the usual graph distance. It is proved that a chordal graph has hyperbolicity at most two. The paper also characterizes which chordal graphs have hyperbolicity one, in terms of forbidden isometric subgraphs.