The hypergraph of θ-classes and θ-graphs of partial cubes.
Boštjan Brešar, Tadeja Kraner Šumenjak · Ars Combinatoria · 2014
Given a partial cube G, the Θ-graph of G has Θ-classes of G as its vertices, and two vertices in it are adjacent if the corresponding Θ-classes meet in a vertex of G. We present a counter-example to the question from [8] whether Θ-graphs of graphs of acyclic cubical complexes are always dually chordal graphs. On a positive side, we show that in the class of ACC pexpansion graphs each Θ-graph is both a dually chordal and a chordal graph. In the proof a fundamental characterization of α-acyclic hypergraphs is combined with techniques from metric graph theory. Along the way, we also introduce a new, weaker version of simplicial elimination scheme which yields yet another characterization of chordal graphs.