In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes. Chordal graphs are a subset of the perfect graphs. They are sometimes also called triangulated graphs.
Contents |
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 later than v in the order form a clique. A graph is chordal if and only if it has a perfect elimination ordering (Fulkerson and Gross 1965).
Rose et al. (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 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. 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 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 (Maffray 2003).
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. As Gavril showed, 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
The interval graphs are the intersection graphs of subtrees of path graphs, a special case of trees; therefore, they are a subfamily of the chordal graphs.
The split graphs are exactly the graphs that are both chordal and the complements of chordal graphs. Bender et al. (1985) showed that, in the limit as n goes to infinity, the fraction of n-vertex chordal graphs that are split approaches one.
The quasi-threshold graphs are exactly the graphs that are both chordal and cographs.
The Strongly Chordal Graphs are graphs that are chordal and contain no n-sun (n>=3) as induced subgraph.
Superclasses
The chordal graphs are a subclass of the even-hole-free graphs, as chordal graphs can contain neither odd nor even holes.
References
- Bender, E. A.; Richmond, L. B.; Wormald, N. C. (1985). "Almost all chordal graphs split". J. Austral. Math. Soc., Series A 38 (2): 214–221. doi:. MR0770128.
- Chandran, L. S.; Ibarra, L.; Ruskey, F.; Sawada, J. (2003). "Enumerating and characterizing the perfect elimination orderings of a chordal graph". Theoretical Computer Science 307: 303–317. doi:. http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf.
- Fulkerson, D. R.; Gross, O. A. (1965). "Incidence matrices and interval graphs". Pacific J. Math 15: 835–855. http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572.
- 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:.
- 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". Theor. Comput. Sci. 234: 59–84. doi:. http://www.cs.colostate.edu/~rmm/lexbfs.ps.
- Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L., Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, 11, Springer-Verlag, pp. 65–84, doi:.
- Rose, D.; Lueker, George; Tarjan, Robert E. (1976). "Algorithmic aspects of vertex elimination on graphs". SIAM J. Computing 5: 266–283. doi:.
External links
- Weisstein, Eric W., "Chordal Graph" from MathWorld.
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
