Transchordal graphs (Q1567619): Difference between revisions

It is known that chordal graphs are intersection graphs of connected subgraphs of trees. They can be extended to the family of transchordal graphs by replacing tree representations with circuit bases. The exact formal definition by using three conditions (intersection, circuit and cover condition) linking a transchordal graph to its graph-and-circuit-basis representation in order to extend what happens for chordal graphs is given in Section 2. For it the notions of host graph, guest graph and host pair for a guest graph are introduced. In Theorem 1 it is proved that every transchordal graph has a special host pair, a so-called \({\mathfrak C}\)-host pair. In Section 3 the structure of these \({\mathfrak C}\)-host pairs and with it the connection between guest transchordal graph and the host representation are investigated and it is shown how \({\mathfrak C}\)-hosts generalize the notion of clique trees for chordal graphs. In Section 4 a basic construction of these host representations is described. It is proved how the basic construction produces \({\mathfrak C}\)-hosts for transchordal graphs (Theorem 5). In the final section, Section 5, Theorem 6 gives a combinatorial characterization of transchordal graphs that resembles two previous characterizations of chordal graphs.