The forbidden-isometric-subgraph characterization of half-hyperbolic 6-chordal graphs
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 for 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 -chordal graph is -hyperbolic if and only if it does not contain any of the ten special graphs , , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.