Chordal graph

Maximal cliques and graph coloring

Another application of perfect elimination orderings is finding a maximum clique of a chordal graph in polynomial-time, while the same problem for general graphs is NP-complete. More generally, a chordal graph can have only linearly many maximal cliques, while non-chordal graphs may have exponentially many. This implies that the class of chordal graphs has few cliques. To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form a clique for each vertex v together with the neighbors of v that are later than v in the perfect elimination ordering, and test whether each of the resulting cliques is maximal.

The clique graphs of chordal graphs are the dually chordal graphs.

The largest maximal clique is a maximum clique, and, as chordal graphs are perfect, the size of this clique equals the chromatic number of the 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.

The chromatic polynomial of a chordal graph is easy to compute. Find a perfect elimination ordering v₁, v₂, …, v_n. Let N_i equal the number of neighbors of v_i that come after v_i in that ordering. For instance, N_n = 0. The chromatic polynomial equals ${\displaystyle (x-N_1)(x-N_2)\cdots (x-N_n).}$ (The last factor is simply x, so x divides the polynomial, as it should.) Clearly, this computation depends on chordality.

Minimal separators

In any graph, a vertex separator is a set of vertices the removal of which leaves the remaining graph disconnected. According to a theorem of Dirac (1961), chordal graphs are graphs in which each minimal separator is a clique. (Note that a minimal separator is not the same thing as a minimal separating subgraph.) Dirac used this characterization to prove that chordal graphs are perfect.

The family of chordal graphs may be defined inductively as the graphs whose vertices can be divided into three nonempty subsets A, S, and B, such that ⁠${\displaystyle A\cup S}$⁠ and ⁠${\displaystyle S\cup B}$⁠ 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. For this reason, chordal graphs have also sometimes been called decomposable graphs.

Intersection graphs of subtrees

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

From a collection of subtrees of a tree, one can define a subtree graph, which is an intersection graph that has one vertex per subtree and an edge connecting any two subtrees that overlap in one or more nodes of the tree. Gavril showed that the subtree graphs are exactly the chordal graphs.

A representation of a chordal graph as an intersection of subtrees forms a tree decomposition of the graph, with treewidth equal to one less than the size of the largest clique in the graph; the tree decomposition of any graph G can be viewed in this way as a representation of G as a subgraph of a chordal graph. The tree decomposition of a graph is also the junction tree of the junction tree algorithm.

Relation to other graph classes

Subclasses

Interval graphs are the intersection graphs of subtrees of path graphs, a special case of trees. Therefore, they are a subfamily of chordal graphs.

Split graphs are graphs that are both chordal and the complements of chordal graphs. 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.

Ptolemaic graphs are graphs that are both chordal and distance hereditary. Quasi-threshold graphs are a subclass of Ptolemaic graphs that are both chordal and cographs. Block graphs are another subclass of Ptolemaic graphs in which every two maximal cliques have at most one vertex in common. A special type is windmill graphs, where the common vertex is the same for every pair of cliques.

Strongly chordal graphs are graphs that are chordal and contain no n-sun (for n ≥ 3) as an induced subgraph. 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. Apollonian networks are chordal maximal planar graphs, or equivalently planar 3-trees. Maximal outerplanar graphs are a subclass of 2-trees, and therefore are also chordal.

Superclasses

Chordal graphs are a subclass of the well known perfect graphs. Other superclasses of chordal graphs include weakly chordal graphs, cop-win graphs, odd-hole-free graphs, even-hole-free graphs, and Meyniel graphs. Chordal graphs are precisely the graphs that are both odd-hole-free and even-hole-free (see holes in graph theory).

Every chordal graph is a strangulated graph, a graph in which every peripheral cycle is a triangle, because peripheral cycles are a special case of induced cycles. Strangulated graphs are graphs that can be formed by clique-sums of chordal graphs and maximal planar graphs. Therefore, strangulated graphs include maximal planar graphs.

Chordal completions and treewidth

If G is an arbitrary graph, a chordal completion of G (or minimum fill-in) is a chordal graph that contains G as a subgraph. The parameterized version of minimum fill-in is fixed parameter tractable, and moreover, is solvable in parameterized subexponential time. The treewidth of G is one less than the number of vertices in a maximum clique of a chordal completion chosen to minimize this clique 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.