Fact-checked by Grok 2 weeks ago

Chordal graph

A chordal graph is an undirected in which every of length four or more has a , an connecting two non-adjacent vertices of the , ensuring no induced longer than three vertices exist. These , also known as triangulated or rigid-circuit , form an important subclass of perfect , where the chromatic number equals the number for every . Chordal graphs are characterized by the existence of a perfect elimination ordering (PEO), a vertex ordering where, for each , its later neighbors form a , allowing linear-time recognition and efficient algorithms for problems like maximum finding. They also admit a clique tree representation, where maximal s are nodes in a such that intersections of cliques along paths satisfy the induced subtree property, facilitating decompositions useful in . Every chordal graph has at least two simplicial vertices—those whose neighbors induce a —and minimal vertex separators are themselves s. The study of chordal graphs dates to the , with early work by Berge linking them to perfect graphs and applications, and key characterizations as intersection graphs of subtrees in a emerging in the from Dirac, Gavril, and others. Notable applications include sparse matrix factorizations like zero-fill , semidefinite optimization for exploiting sparsity, matrix completion, and probabilistic graphical models such as Bayesian networks. In , chordal structures enable polynomial-time solutions for vertex coloring, , and related problems that are NP-hard in general graphs.

Definition and Characterizations

Formal Definition

A chordal graph is an undirected simple graph in which every of length at least four has at least one , an that connects two non-adjacent vertices of the . The concept was first studied in 1958 by Hajnal and Surányi, who characterized such graphs as those without induced of length greater than or equal to four, though the term "chordal" was coined later by Gavril in 1974 to distinguish them from other uses of "triangulated graphs," with earlier names including "rigid circuit graphs" as used by Dirac in 1961. Examples of chordal graphs include complete graphs, which contain no chordless cycles of length four or more since all possible edges are present, and , which are acyclic and thus trivially satisfy the condition. Interval graphs, defined as intersection graphs of intervals on the real line, form a proper subclass of chordal graphs. In contrast, any C_n for n \geq 4 without additional edges is non-chordal, with C_4 being the smallest such example as it forms an induced cycle lacking a chord. Equivalently, chordal graphs are precisely the undirected that contain no induced of length four or more (i.e., no chordless of that length).

Perfect Elimination Ordering

A perfect elimination ordering (PEO) of an undirected G = (V, E) is a linear ordering of the v_1, v_2, \dots, v_n such that, for each index i = 1, 2, \dots, n, the neighbors of v_i that appear after v_i in the ordering (i.e., in \{v_{i+1}, \dots, v_n\}) induce a in G. This ordering captures a structural property where each can be "eliminated" without introducing chords to non-adjacent neighbors later in the sequence. A fundamental characterization of chordal graphs is that a graph is chordal if and only if it admits a PEO. This equivalence is proved using a simplicial elimination scheme: starting from a chordal , repeatedly remove a simplicial —a whose entire neighborhood induces a —yields a PEO in reverse, and the process preserves chordality. Every chordal contains at least one simplicial , and if the graph is non-complete and has at least two vertices, it contains at least two non-adjacent simplicial vertices. Thus, a PEO can be constructed by iteratively selecting and eliminating such vertices until the graph is empty, though efficient linear-time algorithms for finding a PEO are discussed in later sections on . As an illustrative example, consider , which are chordal graphs. In a tree, leaves are simplicial vertices, and any ordering obtained by repeatedly removing leaves—such as a leaf-to-root traversal in a rooted —serves as a PEO, since the later neighbors of each vertex (its or children toward the ) always form a trivial . This highlights how the PEO property aligns with the acyclic structure of trees while generalizing to more complex chordal graphs.

Subtree Intersection Graphs

A chordal graph can be characterized as the of subtrees of a , where each of the corresponds to a subtree, and two vertices are adjacent their corresponding subtrees have a non-empty . This equivalence was established by Gavril in 1974, who proved that a graph is chordal it is the of subtrees in some . A specific construction realizing this characterization is the clique tree of the chordal graph, also known as the intersection tree. In this representation, the nodes of the tree are the maximal cliques of the graph, and each edge connects two maximal cliques whose intersection is a minimal separator of the graph. For each v in the original graph, the subtree corresponding to v consists of all nodes (maximal cliques) in the clique tree that contain v, forming a connected subtree due to the properties of chordal graphs. An illustrative example arises with interval graphs, a subclass of chordal graphs, where the host tree is a and the subtrees are subpaths (intervals) on that path. For arbitrary chordal graphs, the host tree in the subtree intersection representation is a more general beyond a mere path.

Recognition and Computation

Algorithms for Recognition

A chordal graph can be recognized efficiently using ordering-based algorithms that attempt to produce a perfect elimination ordering (PEO) and verify its validity. These methods leverage the characterization that a graph is chordal it admits a PEO, allowing recognition in linear time relative to the number of vertices n and edges m. One such algorithm is the Maximum Cardinality Search (MCS), which iteratively selects the with the largest number of already numbered neighbors as the next in the ordering, starting from an arbitrary and proceeding backwards. If the resulting ordering is a PEO, the is chordal; otherwise, it is not. MCS can be implemented to run in O(n + m) time by maintaining a list of vertices sorted by their labels using appropriate data structures. An alternative is the Lexicographic (Lex-BFS), which performs a while prioritizing vertices with the lexicographically largest labels based on the order in which their neighbors were visited. Like MCS, Lex-BFS produces a PEO for chordal graphs and can be executed in O(n + m) time, making it suitable for recognition. To verify whether an ordering \sigma is a PEO, the algorithm checks for each vertex v (in the reverse order of \sigma) that the neighbors of v that appear later in \sigma form a . This is done by ensuring that the first such neighbor is adjacent to all others, which can be confirmed by examining adjacency lists in O(n + m) total time across all vertices. Both MCS and Lex-BFS were introduced as linear-time recognition algorithms for chordal graphs by , Tarjan, and Lueker. Their correctness relies on the property that, for a chordal graph, these searches yield a PEO; if the verification fails, the graph contains a chordless of length at least four, as the failure point identifies non-adjacent neighbors that, together with earlier vertices, form such a .

Computing Elimination Orderings and Cliques

Assuming the graph is chordal, a perfect elimination ordering (PEO) can be computed efficiently using the maximum cardinality search (MCS) algorithm, which runs in O(n + m) time. The MCS proceeds as follows: initialize all vertices with label 0; for i from n down to 1, select an unnumbered vertex v with the maximum label, assign it the number i, and increment the labels of all its unnumbered neighbors by 1. The resulting ordering \sigma, where vertices are numbered from 1 to n, has the property that the reverse ordering (eliminating low-numbered vertices first) is a PEO. In chordal graphs, MCS always produces a valid PEO, and the algorithm's simplicity enables implementation with appropriate data structures, such as buckets for labels. Given a PEO \alpha = v_1, \dots, v_n (where v_1 is eliminated first), the cliques formed during elimination are the sets C_i = \{v_i\} \cup N^+(v_i), where N^+(v_i) is the set of neighbors of v_i that appear after v_i in \alpha. Each C_i induces a , and the maximal cliques are precisely those C_i that are not properly contained in any other C_j. Since there are at most n such sets and their total description size is O(n + m), the maximal cliques can be identified in linear time by checking containments. These maximal cliques can subsequently be connected via their intersections to form a representation of the . The enumeration runs in O(n + m) time by scanning the adjacency lists along the PEO. For example, consider a chordal graph with vertices \{a, b, c, d\} and edges \{a-b, a-c, b-c, b-d\}. Applying MCS (starting arbitrarily with b numbered 4, labels of a, c, d to 1; then a numbered 3, label of c to 2; then c numbered 2; then d numbered 1), the PEO is d, c, a, b (positions 1 to 4). The sets are: C_d = \{d, b\}; C_c = \{c, a, b\} (since N^+(c) = \{a, b\}); C_a = \{a, b\}; C_b = \emptyset. Among these, \{d, b\} and \{c, a, b\} are maximal, as \{a, b\} is contained in \{c, a, b\}.

Structural Properties

Maximal Cliques and Separators

In chordal graphs, the maximal cliques form the fundamental building blocks of the graph's structure and can be enumerated efficiently. Specifically, given a perfect elimination ordering, an can list all maximal cliques in linear time relative to the size of the graph, by identifying the neighborhoods of vertices during the elimination process. This efficiency stems from the fact that each maximal clique corresponds to a simplicial vertex's neighborhood at the time of its elimination, allowing the cliques to be output without . A minimal in a is defined as an inclusion-minimal vertex set whose removal disconnects two non-adjacent vertices, thereby separating them into different connected components. In chordal graphs, every such minimal separator induces a complete , or . Moreover, these minimal separators are exactly the cliques that separate distinct components of the graph after removal, ensuring that no smaller subset achieves the same disconnection. This property distinguishes chordal graphs, as non-chordal graphs may have minimal separators that are not cliques. In a connected chordal graph, the number of edges in any clique tree equals the number of maximal cliques minus one, and each such edge is labeled by a minimal separator given by the intersection of the two adjacent maximal cliques (with possible repetitions of the same separator on multiple edges). Thus, the number of distinct minimal separators is at most the number of maximal cliques minus one. This arises from the tree-like organization in the clique tree representation, where maximal cliques are nodes and minimal separators label the edges connecting adjacent nodes. Chordal graphs exhibit the running among their maximal s, meaning there exists a linear ordering of the cliques such that, for each clique beyond the first, its with the union of all preceding cliques is contained entirely within the immediately previous clique. This facilitates the construction of clique trees and underscores the -based characterizations of chordal graphs. For instance, in the clique tree of a chordal graph—where nodes represent maximal cliques and edges connect cliques whose is nonempty—the minimal associated with each tree edge is precisely the of the two adjacent maximal cliques. This serves as the separator between the subtrees rooted at those nodes, illustrating how separators bridge the clique structure.

Coloring and Perfectness

Chordal graphs possess a perfect elimination ordering (PEO), which enables an efficient for . Given a PEO \sigma = v_1, v_2, \dots, v_n of the graph G, where v_1 is simplicial and for each i > 1, the neighbors of v_i in \{v_1, \dots, v_{i-1}\} induce a , the coloring proceeds in the reverse order v_n, v_{n-1}, \dots, v_1. For each v_i, assign the smallest color not used by its already colored neighbors (those in \{v_{i+1}, \dots, v_n\}). The PEO property ensures that these neighbors induce a in the subgraph remaining at that step, so at most \omega(G) colors are needed, where \omega(G) is the size of the largest in G. This approach yields an optimal coloring, as the number of colors used equals \omega(G). A proof proceeds by on the number of vertices: for the base case of a single , \chi(G) = \omega(G) = 1; assuming the result holds for n-1 vertices, remove a simplicial v_n whose neighbors form a of size at most \omega(G) - 1, color the remaining optimally with \omega(G \setminus v_n) colors, and extend the coloring to v_n using an available color without exceeding \omega(G). By , \chi(G \setminus v_n) = \omega(G \setminus v_n) \leq \omega(G). The neighbors of v_n form a of size at most \omega(G) - 1, so they use at most \omega(G) - 1 colors, leaving at least one color available among the \omega(G) colors for v_n. Chordal graphs are perfect, meaning that for every induced subgraph H, the chromatic number \chi(H) equals the clique number \omega(H). This follows from the PEO characterization, which restricts to a PEO of any induced subgraph, ensuring optimal coloring as above. Additionally, chordal graphs contain no induced cycles of length at least four, hence no odd holes (induced odd cycles of length at least five) or their complements (odd antiholes), so perfection holds by the strong perfect graph theorem. The coloring algorithm runs in O(n + m) time, where n is the number of vertices and m the number of edges, as a PEO can be computed in linear time using , and the is a single pass over the vertices and their adjacency lists. This polynomial-time solvability extends to other NP-hard problems on general graphs, such as and , which reduce to coloring on chordal graphs.

Relations to Other Graph Classes

Subclasses

Interval graphs form an important subclass of chordal graphs, defined as the intersection graphs of closed intervals on the real line, where each corresponds to an interval and edges connect intervals that intersect. This representation ensures that interval graphs are chordal, as any induced cycle of length four or more would contradict the linear ordering of intervals without chords. Additionally, interval graphs are characterized by the consecutive ones property: there exists a row of the -clique such that the 1's in each row appear consecutively. This property enables linear-time recognition algorithms and underscores their additional structural simplicity compared to general chordal graphs. Split graphs constitute another fundamental subclass of chordal graphs, where the vertex set can be partitioned into a K and an independent set I, with edges between K and I being arbitrary. All split graphs are chordal because they are (2K_2, C_4, C_5)-free, avoiding the induced cycles that characterize non-chordal graphs. This partition provides a structure, facilitating efficient algorithms for optimization problems like coloring, where the chromatic number equals the clique number. Threshold graphs are a proper subclass of graphs (and thus chordal), obtainable by starting from the empty graph and repeatedly adding either an isolated or a dominating (adjacent to all existing vertices). They are characterized by degree sequences satisfying specific conditions or as (2K_2, P_4, C_4)-free graphs. This construction yields even more restricted structure, with threshold graphs exhibiting unique properties like being both and cographs, enabling constant-time recognition via sequences. Chordal bipartite graphs represent the bipartite subclass of chordal graphs, consisting of bipartite graphs with no induced of length six or longer. As a -like subclass in the sense that their structure often decomposes into representations of bipartite s, they inherit chordality while maintaining bipartiteness, and admit efficient algorithms for matching and flow problems due to their acyclic chordal nature in even cycles. These subclasses collectively exhibit enhanced computational tractability over general chordal graphs, such as polynomial-time solutions for problems like maximum via their or models.

Superclasses

Chordal graphs form a subclass of perfect graphs, where a graph is perfect if, for every , the equals the . This inclusion follows from the property that chordal graphs admit a perfect elimination ordering, which enables to achieve the optimal chromatic number equal to the size of the maximum . The perfection of chordal graphs was established early in the study of perfect graphs, predating the strong perfect graph theorem. Weakly chordal graphs provide another superclass of chordal graphs, defined as graphs in which neither the graph nor its complement contains an induced of length at least five (known as holes or antiholes). Chordal graphs satisfy this since they contain no induced cycles of length four or more, making them a proper subclass. Weakly chordal graphs generalize chordal graphs by allowing certain induced cycles of length four while still ensuring perfectness and efficient algorithmic solvability for optimization problems like coloring. Meyniel graphs constitute yet another superclass, characterized by the condition that every odd cycle of length at least five has at least two chords. Chordal graphs vacuously satisfy this, as they have no such cycles, and Meyniel graphs are known to be perfect. This class relaxes the chordal condition by permitting some odd holes with multiple chords. The classes of chordal graphs and s are incomparable: not every planar graph is chordal, as the C_5 is planar but induces a chordless cycle of length five, and not every chordal graph is planar, as the K_5 is chordal but non-planar by Kuratowski's theorem.

Completions and Width Parameters

Chordal Completions

A chordal of an undirected G is a chordal supergraph on the same vertex set that includes all edges of G, obtained by adding a set of edges to eliminate induced cycles of length four or more. A minimal chordal is one where removing any added edge results in a non-chordal , ensuring no superfluous edges are introduced. The minimum fill-in problem seeks a chordal with the smallest number of added edges, which is NP-complete. This complexity arises from the challenge of optimally triangulating the while minimizing structural increases. Approximations for the minimum fill-in can leverage related parameters, though exact solutions remain intractable for general . To compute a minimal chordal , the MCS-M employs maximum search (MCS), an ordering that simulates elimination and identifies necessary fill-in edges. During the process, MCS labels vertices by selecting those adjacent to the most previously labeled vertices, revealing a perfect elimination ordering (PEO) in chordal or adding edges to enforce one in non-chordal cases. This approach runs in linear time relative to the size and produces a minimal set of fill-ins by verifying irredundancy at each step. Every admits a chordal , as adding edges to form a yields a trivial chordal supergraph. More refined completions relate to graphs embeddable as partial k-trees for some k, where the added edges bound the resulting structure. Chordal completions find key applications in , particularly of symmetric positive definite matrices, where fill-in edges correspond to nonzeros introduced during elimination. By computing a chordal via an appropriate ordering, such as one from MCS, the avoids excessive density while preserving sparsity patterns, enabling efficient numerical solutions in large-scale computations.

Treewidth Connection

Treewidth is a graph parameter that measures the "tree-likeness" of a graph, defined as the minimum width over all possible tree decompositions of the graph, where the width of a decomposition is the size of the largest bag minus one. For chordal graphs, this parameter has a particularly simple characterization: the treewidth equals the size of the largest clique minus one, denoted \tw(G) = \omega(G) - 1. This equality holds because in a chordal graph, a clique tree provides an optimal tree decomposition where each bag is a maximal clique, ensuring that the maximum bag size is precisely \omega(G). A fundamental structural theorem links chordality directly to tree decompositions: a graph is chordal if and only if it admits a tree decomposition in which every bag induces a clique, known as a clique tree. In such a decomposition, the nodes of the tree correspond to the maximal cliques of the graph, and the intersection properties ensure that the decomposition satisfies the running intersection property required for tree decompositions. This characterization not only confirms the treewidth formula but also provides a combinatorial representation of chordal graphs that facilitates algorithmic exploitation of their structure. Computing the treewidth of a chordal graph is thus equivalent to finding the size of its maximum , which can be done efficiently using algorithms based on perfect elimination orderings. For general graphs, treewidth computation is NP-hard, but chordal graphs serve as approximations: the treewidth of any graph is the minimum over all chordal supergraphs H of \omega(H) - 1. This connection underscores the role of chordal graphs in bounding for broader classes. The treewidth connection enables powerful algorithmic techniques for chordal graphs, particularly dynamic programming over the clique tree to solve optimization problems such as maximum independent set or in time polynomial in the graph size and exponential only in the treewidth (which is \omega(G) - 1). This approach leverages the bounded size of cliques in the bags, making chordal graphs amenable to exact solutions for NP-hard problems when the clique number is small.