The forbidden-isometric-subgraph characterization of half-hyperbolic 6-chordal graphs

Let a graph be 6-chordal if every cycle of length at least six has a chord, and let graph hyperbolicity be measured in the usual graph metric. Let G1,G2,G3,C4,C6,HiG_1,G_2,G_3,C_4,C_6,H_i for i=1,,5i=1,\ldots,5 be the ten special graphs depicted or defined in the paper. An isometric subgraph is a subgraph whose induced distances agree with the distances in the ambient graph.

Forbidden-subgraph conjecture. A 66-chordal graph is 12\frac{1}{2}-hyperbolic if and only if it does not contain any of the ten special graphs G1,G2,G3,C4,C6,HiG_1,G_2,G_3,C_4,C_6,H_i, i=1,,5i=1,\ldots,5, as an isometric subgraph.

The claim gives a finite forbidden-isometric-subgraph characterization of half-hyperbolic graphs within the class of 6-chordal graphs. The supplied source context does not indicate whether this conjecture has been proved or disproved.

Sources & referencesView supporting material

Primary source

Yaokun Wu and Chengpeng Zhang, “Chordality and hyperbolicity of a graph”, arXiv:0910.3544 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.