Chordal graph

Last updated February 08, 2024

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs^[1] or triangulated graphs:^[2] a chordal completion of a graph is typically called a triangulation of that graph.

Chordal graphs are a subset of the perfect graphs. 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. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it.

Perfect elimination and efficient recognition

A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex $v$ , $v$ and the neighbors of $v$ that occur after $v$ in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering.^[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. This algorithm maintains a partition of the vertices of the graph into a sequence of sets; initially this sequence consists of a single set with all vertices. 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. When this splitting process has been performed for all vertices, the sequence of sets has one vertex per set, in the reverse of a perfect elimination ordering.

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. The graph sandwich problem on chordal graphs is NP-complete ^[4] whereas the probe graph problem on chordal graphs has polynomial-time complexity.^[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.

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.^[6]

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.^[7]

The chromatic polynomial of a chordal graph is easy to compute. Find a perfect elimination ordering $v 1, v 2, \dots, 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 $(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.^[8]

Minimal separators

In any graph, a vertex separator is a set of vertices the removal of which leaves the remaining graph disconnected; a separator is minimal if it has no proper subset that is also a separator. According to a theorem of Dirac (1961), chordal graphs are graphs in which each minimal separator is a clique; 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 $A\cup S$ and $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.^[9]

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 \geq 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.^[10] Apollonian networks are chordal maximal planar graphs, or equivalently planar 3-trees.^[10] 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.^[11]

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.^[12]^[13] 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.^[14]

Notes

↑ Dirac (1961)
↑ Berge (1967).
↑ Rose (1970).
↑ Bodlaender, Fellows & Warnow (1992).
↑ Berry, Golumbic & Lipshteyn (2007).
↑ Szwarcfiter & Bornstein (1994).
↑ Maffray (2003).
↑ For instance, Agnarsson (2003), Remark 2.5, calls this method well known.
↑ Peter Bartlett. "Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations" (PDF).
1 2 Patil (1986).
↑ Seymour & Weaver (1984).
↑ Kaplan, Shamir & Tarjan (1999).
↑ Fomin & Villanger (2013).
↑ Parra & Scheffler (1997).

Related Research Articles

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set $of vertices such that for every two vertices in, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.$

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly $k$ are called $k$ -trees, and the graphs with treewidth at most $k$ are called partial $k$ -trees. Many other well-studied graph families also have bounded treewidth.

In constraint satisfaction, a decomposition method translates a constraint satisfaction problem into another constraint satisfaction problem that is binary and acyclic. Decomposition methods work by grouping variables into sets, and solving a subproblem for each set. These translations are done because solving binary acyclic problems is a tractable problem.

In graph theory, a path decomposition of a graph $G$ is, informally, a representation of $G$ as a "thickened" path graph, and the pathwidth of $G$ is a number that measures how much the path was thickened to form $G$ . More formally, a path-decomposition is a sequence of subsets of vertices of $G$ such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979), where they called these graphs "polar graphs".

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$ (denoted by $i (v)$ )
Disjoint union of two labeled graphs $G$ and $H$ (denoted by $)$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ (denoted by $η (i, j)$ ), where $i \neq j$
Renaming label $i$ to label $j$ (denoted by $ρ (i, j)$ )

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an $n$ -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In the mathematical area of graph theory, an undirected graph $G$ is strongly chordal if it is a chordal graph and every cycle of even length in $G$ has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

In graph theory, the tree-depth of a connected undirected graph $is a numerical invariant of, the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages. Intuitively, where the treewidth of a graph measures how far it is from being a tree, this parameter measures how far a graph is from being a star.$

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph $G$ is a chordal graph, on the same vertex set, that has $G$ as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

References

Agnarsson, Geir (2003), "On chordal graphs and their chromatic polynomials", Mathematica Scandinavica, 93 (2): 240–246, doi: 10.7146/math.scand.a-14421 , MR 2009583 .
Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985), "Almost all chordal graphs split", J. Austral. Math. Soc., A, 38 (2): 214–221, doi: 10.1017/S1446788700023077 , MR 0770128 .
Berge, Claude (1967), "Some Classes of Perfect Graphs", in Harary, Frank (ed.), Graph Theory and Theoretical Physics, Academic Press, pp. 155–165, MR 0232694 .
Berry, Anne; Golumbic, Martin Charles; Lipshteyn, Marina (2007), "Recognizing chordal probe graphs and cycle-bicolorable graphs", SIAM Journal on Discrete Mathematics , 21 (3): 573–591, doi:10.1137/050637091 .
Bodlaender, H. L.; Fellows, M. R.; Warnow, T. J. (1992), "Two strikes against perfect phylogeny" (PDF), Proc. of 19th International Colloquium on Automata Languages and Programming , Lecture Notes in Computer Science, vol. 623, pp. 273–283, doi:10.1007/3-540-55719-9_80, hdl: 1874/16653 .
Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003), "Enumerating and characterizing the perfect elimination orderings of a chordal graph" (PDF), Theoretical Computer Science , 307 (2): 303–317, doi:10.1016/S0304-3975(03)00221-4 .
Dirac, G. A. (1961), "On rigid circuit graphs", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 25 (1–2): 71–76, doi:10.1007/BF02992776, MR 0130190, S2CID 120608513 .
Fomin, Fedor V.; Villanger, Yngve (2013), "Subexponential Parameterized Algorithm for Minimum Fill-In", SIAM J. Comput., 42 (6): 2197–2216, arXiv: 1104.2230 , doi:10.1137/11085390X, S2CID 934546 .
Fulkerson, D. R.; Gross, O. A. (1965), "Incidence matrices and interval graphs", Pacific J. Math., 15 (3): 835–855, doi: 10.2140/pjm.1965.15.835 .
Gavril, Fănică (1974), "The intersection graphs of subtrees in trees are exactly the chordal graphs", Journal of Combinatorial Theory , Series B, 16: 47–56, doi: 10.1016/0095-8956(74)90094-X .
Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press.
Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing", Theoretical Computer Science , 234 (1–2): 59–84, doi: 10.1016/S0304-3975(97)00241-7 .
Kaplan, Haim; Shamir, Ron; Tarjan, Robert (1999), "Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs", SIAM J. Comput., 28 (5): 1906–1922, doi:10.1137/S0097539796303044 .
Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3, ISBN 0-387-95434-1 .
Parra, Andreas; Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics, 79 (1–3): 171–188, doi: 10.1016/S0166-218X(97)00041-3 , MR 1478250 .
Patil, H. P. (1986), "On the structure of k-trees", Journal of Combinatorics, Information and System Sciences, 11 (2–4): 57–64, MR 0966069 .
Rose, Donald J. (December 1970), "Triangulated graphs and the elimination process", Journal of Mathematical Analysis and Applications, 32 (3): 597–609, doi:10.1016/0022-247x(70)90282-9
Rose, D.; Lueker, George; Tarjan, Robert E. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing , 5 (2): 266–283, doi:10.1137/0205021, MR 0408312 .
Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory , 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878 .
Szwarcfiter, J.L.; Bornstein, C.F. (1994), "Clique graphs of chordal and path graphs", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, doi:10.1137/s0895480191223191, hdl: 11422/1497 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[dirac-1] Dirac (1961)

[berge-2] Berge (1967).

[FOOTNOTERose1970-3] Rose (1970).

[FOOTNOTEBodlaenderFellowsWarnow1992-4] Bodlaender, Fellows & Warnow (1992).

[FOOTNOTEBerryGolumbicLipshteyn2007-5] Berry, Golumbic & Lipshteyn (2007).

[FOOTNOTESzwarcfiterBornstein1994-6] Szwarcfiter & Bornstein (1994).

[FOOTNOTEMaffray2003-7] Maffray (2003).

[8] For instance, Agnarsson (2003), Remark 2.5, calls this method well known.

[9] Peter Bartlett. "Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations" (PDF).

[patil86-10] 1 2 Patil (1986).

[FOOTNOTESeymourWeaver1984-11] Seymour & Weaver (1984).

[FOOTNOTEKaplanShamirTarjan1999-12] Kaplan, Shamir & Tarjan (1999).

[FOOTNOTEFominVillanger2013-13] Fomin & Villanger (2013).

[FOOTNOTEParraScheffler1997-14] Parra & Scheffler (1997).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]