Dually chordal graph

The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques is the dual of a hypertree.

Originally, these graphs were defined by maximum neighborhood orderings and have a variety of different characterizations.

In De Caria & Gutierrez (2012) dually chordal graphs are characterized in terms of separator properties.

[5] While some basic problems such as maximum independent set, maximum clique, coloring and clique cover remain NP-complete for dually chordal graphs, some variants of the minimum dominating set problem and Steiner tree are efficiently solvable on dually chordal graphs (but Independent Domination remains NP-complete).

[6] See Brandstädt, Chepoi & Dragan (1999) for the use of dually chordal graph properties for tree spanners, and see Brandstädt, Leitert & Rautenbach (2012) for a linear time algorithm of efficient domination and efficient edge domination on dually chordal graphs.