Chordal graph

They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal.

[3] Rose, Lueker & Tarjan (1976) (see also Habib et al. 2000) show that a perfect elimination ordering of a chordal graph may be found efficiently using an algorithm known as lexicographic breadth-first search.

The algorithm repeatedly chooses a vertex v from the earliest set in the sequence that contains previously unchosen vertices, and splits each set S of the sequence into two smaller subsets, the first consisting of the neighbors of v in S and the second consisting of the non-neighbors.

Since both this lexicographic breadth first search process and the process of testing whether an ordering is a perfect elimination ordering can be performed in linear time, it is possible to recognize chordal graphs in linear time.

[5] The set of all perfect elimination orderings of a chordal graph can be modeled as the basic words of an antimatroid; Chandran et al. (2003) use this connection to antimatroids as part of an algorithm for efficiently listing all perfect elimination orderings of a given chordal graph.

Chordal graphs are perfectly orderable: an optimal coloring may be obtained by applying a greedy coloring algorithm to the vertices in the reverse of a perfect elimination ordering.

[7] The chromatic polynomial of a chordal graph is easy to compute.

⁠ both form chordal induced subgraphs, S is a clique, and there are no edges from A to B.

That is, they are the graphs that have a recursive decomposition by clique separators into smaller subgraphs.

[9] An alternative characterization of chordal graphs, due to Gavril (1974), involves trees and their subtrees.

Bender, Richmond & Wormald (1985) showed that, in the limit as n goes to infinity, the fraction of n-vertex chordal graphs that are split approaches one.

A special type is windmill graphs, where the common vertex is the same for every pair of cliques.

Here an n-sun is an n-vertex chordal graph G together with a collection of n degree-two vertices, adjacent to the edges of a Hamiltonian cycle in G. K-trees are chordal graphs in which all maximal cliques and all maximal clique separators have the same size.

The k-trees are the graphs to which no additional edges can be added without increasing their treewidth to a number larger than k. Therefore, the k-trees are their own chordal completions, and form a subclass of the chordal graphs.

Chordal completions can also be used to characterize several other related classes of graphs.

A cycle (black) with two chords (green). As for this part, the graph is chordal. However, removing one green edge would result in a non-chordal graph. Indeed, the other green edge with three black edges would form a cycle of length four with no chords.
A chordal graph with eight vertices, represented as the intersection graph of eight subtrees of a six-node tree.