The Hypergraph of $\mathrm{\Theta }$-Classes and $\mathrm{\Theta }$-Graphs of Partial Cubes

Abstract

Given a partial cube $G$, the $\mathrm{\Theta }$-graph of $G$ has $\mathrm{\Theta }$-classes of $G$ as its vertices, and two vertices in it are adjacent if the corresponding $\mathrm{\Theta }$-classes meet in a vertex of $G$. We present a counter-example to the question from $[8]$ whether $\mathrm{\Theta }$-graphs of graphs of acyclic cubical complexes are always dually chordal graphs. On a positive side, we show that in the class of ACC $p$-expansion graphs, each $\mathrm{\Theta }$-graph is both a dually chordal and a chordal graph. In the proof, a fundamental characterization of $\mathrm{\Theta }$-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.