Editing Chordal graph

{{Short description|Graph where all long cycles have a chord}}
[[Image:Chordal-graph.svg|thumb|220px|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.]]
In the [[mathematics|mathematical]] area of [[graph theory]], a '''chordal graph''' is one in which all [[cycle (graph theory)|cycles]] of four or more [[vertex (graph theory)|vertices]] have a ''chord'', which is an [[edge (graph theory)|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 (graph theory)|clique]], and as the [[intersection graph]]s of subtrees of a tree.  They are sometimes also called '''rigid circuit graphs'''<ref name="dirac">{{harvtxt|Dirac|1961}}</ref> or  '''triangulated graphs''':<ref name="berge">{{harvtxt|Berge|1967}}.</ref> a chordal completion of a graph is typically called a '''triangulation''' of that graph.

Chordal graphs are a subset of the [[perfect graph]]s. 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 [[clique (graph theory)|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 {{mvar|v}}, {{mvar|v}} and the [[Neighborhood (graph theory)|neighbors]] of {{mvar|v}} that occur after {{mvar|v}} in the order form a [[Clique (graph theory)|clique]]. A graph is chordal [[if and only if]] it has a perfect elimination ordering.{{sfnp|Rose|1970}}

{{harvtxt|Rose|Lueker|Tarjan|1976}} (see also {{harvnb|Habib|McConnell|Paul|Viennot|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 {{mvar|v}} from the earliest set in the sequence that contains previously unchosen vertices, and splits each set {{mvar|S}} of the sequence into two smaller subsets, the first consisting of the neighbors of {{mvar|v}} in {{mvar|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]]{{sfnp|Bodlaender|Fellows|Warnow|1992}} whereas the probe graph problem on chordal graphs has polynomial-time complexity.{{sfnp|Berry|Golumbic|Lipshteyn|2007}}

The set of all perfect elimination orderings of a chordal graph can be modeled as the ''basic words'' of an [[antimatroid]]; {{harvtxt|Chandran|Ibarra|Ruskey|Sawada|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 (graph theory)|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 clique]]s, while non-chordal graphs may have exponentially many. This implies that the class of chordal graphs has [[Graphs with few cliques|few cliques]]. To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form a clique for each vertex {{mvar|v}} together with the neighbors of {{mvar|v}} that are later than {{mvar|v}} in the perfect elimination ordering, and test whether each of the resulting cliques is maximal.

The [[clique graph]]s of chordal graphs are the [[dually chordal graph]]s.{{sfnp|Szwarcfiter|Bornstein|1994}}

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 graph|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.{{sfnp|Maffray|2003}}

The [[chromatic polynomial]] of a chordal graph is easy to compute.  Find a perfect elimination ordering {{math|''v''{{sub|1}}, ''v''{{sub|2}}, …, ''v{{sub|n}}''}}.  Let {{mvar|N{{sub|i}}}} equal the number of neighbors of {{mvar|v{{sub|i}}}} that come after {{mvar|v{{sub|i}}}} in that ordering.  For instance, {{math|1=''N{{sub|n}}'' = 0}}.  The chromatic polynomial equals <math>(x-N_1)(x-N_2)\cdots(x-N_n).</math>  (The last factor is simply {{mvar|x}}, so {{mvar|x}} divides the polynomial, as it should.)  Clearly, this computation depends on chordality.<ref>For instance, {{harvtxt|Agnarsson|2003}}, Remark 2.5, calls this method well known.</ref>

==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 {{harvtxt|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 graph|perfect]].

The family of chordal graphs may be defined inductively as the graphs whose vertices can be divided into three nonempty subsets {{mvar|A}}, {{mvar|S}}, and {{mvar|B}}, such that {{tmath|A \cup S}} and {{tmath|S \cup B}} both form chordal [[induced subgraph]]s, {{mvar|S}} is a clique, and there are no edges from {{mvar|A}} to {{mvar|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'''.<ref>{{cite web |url=http://www.stat.berkeley.edu/~bartlett/courses/241A-spring2007/graphnotes.pdf |title=Undirected Graphical Models: Chordal Graphs, Decomposable Graphs, Junction Trees, and Factorizations | author=Peter Bartlett}}</ref>

==Intersection graphs of subtrees==
[[Image:Tree decomposition.svg|thumb|A chordal graph with eight vertices, represented as the intersection graph of eight subtrees of a six-node tree.]]
An alternative characterization of chordal graphs, due to {{harvtxt|Gavril|1974}}, involves [[tree (graph theory)|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 graph]]s are the intersection graphs of subtrees of [[path graph]]s, a special case of trees. Therefore, they are a subfamily of chordal graphs.

[[Split graph]]s are graphs that are both chordal and the [[complement (graph theory)|complements]] of chordal graphs. {{harvtxt|Bender|Richmond|Wormald|1985}} showed that, in the limit as {{mvar|n}} goes to infinity, the fraction of {{mvar|n}}-vertex chordal graphs that are split approaches one.

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

[[Strongly chordal graph]]s are graphs that are chordal and contain no {{mvar|n}}-sun (for {{math|''n'' ≥ 3}}) as an induced subgraph. Here an {{mvar|n}}-sun is an {{mvar|n}}-vertex chordal graph {{mvar|G}} together with a collection of {{mvar|n}} degree-two vertices, adjacent to the edges of a [[Hamiltonian cycle]] in&nbsp;{{mvar|G}}.

[[k-tree|{{mvar|K}}-trees]] are chordal graphs in which all maximal cliques and all maximal clique separators have the same size.<ref name="patil86">{{harvtxt|Patil|1986}}.</ref> [[Apollonian network]]s are chordal maximal [[planar graph]]s, or equivalently planar 3-trees.<ref name="patil86"/> Maximal [[outerplanar graph]]s are a subclass of 2-trees, and therefore are also chordal.

===Superclasses===
Chordal graphs are a subclass of the well known [[perfect graph]]s. 
Other superclasses of chordal graphs include weakly chordal graphs, [[cop-win graph]]s, odd-hole-free graphs, [[even-hole-free graph]]s, and [[Meyniel graph]]s. Chordal graphs are precisely the graphs that are both odd-hole-free and even-hole-free (see [[hole (graph theory)|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-sum]]s of chordal graphs and maximal planar graphs. Therefore, strangulated graphs include [[maximal planar graph]]s.{{sfnp|Seymour|Weaver|1984}}

==Chordal completions and treewidth==
{{main|Chordal completion}}
If {{mvar|G}} is an arbitrary graph, a '''chordal completion''' of {{mvar|G}} (or '''minimum fill-in''') is a chordal graph that contains {{mvar|G}} as a subgraph. The parameterized version of minimum fill-in is [[Parameterized complexity|fixed parameter tractable]], and moreover, is solvable in parameterized subexponential time.{{sfnp|Kaplan|Shamir|Tarjan|1999}}{{sfnp|Fomin|Villanger|2013}}  
The [[treewidth]] of {{mvar|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-tree|{{mvar|k}}-trees]] are the graphs to which no additional edges can be added without increasing their treewidth to a number larger than&nbsp;{{mvar|k}}.
Therefore, the {{mvar|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.{{sfnp|Parra|Scheffler|1997}}

== Notes ==
{{reflist|30em}}

==References==
*{{citation
 | last = Agnarsson | first = Geir
 | issue = 2
 | journal = Mathematica Scandinavica
 | mr = 2009583
 | pages = 240–246
 | title = On chordal graphs and their chromatic polynomials
 | url = http://www.mscand.dk/article/view/14421
 | volume = 93
 | year = 2003| doi = 10.7146/math.scand.a-14421
 | doi-access = free
 }}.
*{{citation
 | last1 = Bender | first1 = E. A.
 | last2 = Richmond | first2 = L. B.
 | last3 = Wormald | first3 = N. C.
 | doi = 10.1017/S1446788700023077
 | mr = 0770128
 | issue = 2
 | journal = J. Austral. Math. Soc.
 | series = A
 | pages = 214–221
 | title = Almost all chordal graphs split
 | volume = 38
 | year = 1985| doi-access = free
 }}.
*{{citation
 | last = Berge | first = Claude
 | contribution = Some Classes of Perfect Graphs
 | editor1-last = Harary | editor1-first = Frank | editor1-link = Frank_Harary
 | pages = 155–165
 | publisher = Academic Press
 | title = Graph Theory and Theoretical Physics
 | year = 1967
 | mr = 0232694}}.
*{{citation
 | last1 = Berry | first1 = Anne 
 | last2 = Golumbic | first2 = Martin Charles | author2-link = Martin Charles Golumbic
 | last3 = Lipshteyn| first3 = Marina 
 | title     = Recognizing chordal probe graphs and cycle-bicolorable graphs
 | journal   = [[SIAM Journal on Discrete Mathematics]]
 | volume    = 21
 | year      = 2007
 | pages     = 573–591
 | doi = 10.1137/050637091
 | issue = 3}}.
*{{citation
 | last1 = Bodlaender | first1 = H. L. | author1-link = Hans L. Bodlaender
 | last2 = Fellows | first2 = M. R. | author2-link = Michael Fellows
 | last3 = Warnow | first3 = T. J. | author3-link = Tandy Warnow
 | contribution = Two strikes against perfect phylogeny
 | doi = 10.1007/3-540-55719-9_80
 | pages = 273–283
 | series = Lecture Notes in Computer Science
 | title = [[International Colloquium on Automata, Languages and Programming|Proc. of 19th International Colloquium on Automata Languages and Programming]]
 | volume = 623
 | year = 1992| hdl = 1874/16653 | contribution-url = https://dspace.library.uu.nl/bitstream/1874/16653/1/bodlaender_92_two%20strikes.pdf
 | hdl-access = free
 }}.
*{{citation
 | last1 = Chandran | first1 = L. S.
 | last2 = Ibarra | first2 = L.
 | last3 = Ruskey | first3 = F. | author3-link = Frank Ruskey
 | last4 = Sawada | first4 = J.
 | doi = 10.1016/S0304-3975(03)00221-4
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 303–317
 | title = Enumerating and characterizing the perfect elimination orderings of a chordal graph
 | url = http://www.cis.uoguelph.ca/~sawada/papers/chordal.pdf
 | volume = 307
 | year = 2003
 | issue = 2}}.
*{{citation
 | last = Dirac | first = G. A. | authorlink = Gabriel Andrew Dirac
 | doi = 10.1007/BF02992776
 | mr = 0130190
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | pages = 71–76
 | title = On rigid circuit graphs
 | volume = 25
 | year = 1961| issue = 1–2 | s2cid = 120608513
 }}.
*{{citation
 | last1 = Fomin | first1 = Fedor V.
 | last2 = Villanger | first2 = Yngve
 | journal = SIAM J. Comput.
 | pages = 2197–2216
 | title = Subexponential Parameterized Algorithm for Minimum Fill-In
 | volume = 42
 | year = 2013
 | issue = 6
 | doi=10.1137/11085390X| arxiv = 1104.2230| s2cid = 934546
 }}.
*{{citation
 | last1 = Fulkerson | first1 = D. R. | author1-link = D. R. Fulkerson
 | last2 = Gross | first2 = O. A.
 | journal = Pacific J. Math.
 | pages = 835–855
 | title = Incidence matrices and interval graphs
 | url = http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572
 | volume = 15
 | year = 1965 | issue = 3 | doi=10.2140/pjm.1965.15.835| doi-access = free
 }}.
*{{citation
 | last = Gavril | first = Fănică
 | doi = 10.1016/0095-8956(74)90094-X
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | pages = 47–56
 | title = The intersection graphs of subtrees in trees are exactly the chordal graphs
 | volume = 16
 | year = 1974| doi-access = free
 }}.
*{{citation
 |first=Martin Charles|last=Golumbic
 |authorlink=Martin Charles Golumbic
 |title=Algorithmic Graph Theory and Perfect Graphs
 |year=1980|publisher=Academic Press}}.
*{{citation
 | last1 = Habib | first1 = Michel
 | last2 = McConnell | first2 = Ross
 | last3 = Paul | first3 = Christophe
 | last4 = Viennot | first4 = Laurent
 | doi = 10.1016/S0304-3975(97)00241-7
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 59–84
 | title = Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition, and consecutive ones testing
 | url = http://www.cs.colostate.edu/~rmm/lexbfs.ps
 | volume = 234
 | year = 2000| issue = 1–2
 | doi-access = free
 }}.
*{{citation
 | last1 = Kaplan | first1 = Haim
 | last2 = Shamir | first2 = Ron
 | last3 = Tarjan | first3 = Robert
 | journal = SIAM J. Comput.
 | pages = 1906–1922
 | title = Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
 | volume = 28
 | year = 1999 | issue = 5
 | doi=10.1137/S0097539796303044}}.
*{{citation
 | last = Maffray | first = Frédéric
 | contribution = On the coloration of perfect graphs
 | doi = 10.1007/0-387-22444-0_3
 | editor1-last = Reed | editor1-first = Bruce A. | editor1-link = Bruce Reed (mathematician)
 | editor2-last = Sales | editor2-first = Cláudia L.
 | pages = 65–84
 | publisher = Springer-Verlag
 | series = CMS Books in Mathematics
 | title = Recent Advances in Algorithms and Combinatorics
 | volume = 11
 | year = 2003
 | isbn = 0-387-95434-1}}.
*{{citation
 | last1 = Parra | first1 = Andreas
 | last2 = Scheffler | first2 = Petra
 | doi = 10.1016/S0166-218X(97)00041-3
 | issue = 1–3
 | journal = Discrete Applied Mathematics
 | mr = 1478250
 | pages = 171–188
 | title = Characterizations and algorithmic applications of chordal graph embeddings
 | volume = 79
 | year = 1997| doi-access = free
 }}.
*{{citation
 | last = Patil | first = H. P.
 | mr = 966069
 | issue = 2–4
 | journal = Journal of Combinatorics, Information and System Sciences
 | pages = 57–64
 | title = On the structure of ''k''-trees
 | volume = 11
 | year = 1986}}.
*{{citation
 | last = Rose | first = Donald J.
 | date = December 1970
 | doi = 10.1016/0022-247x(70)90282-9
 | issue = 3
 | journal = Journal of Mathematical Analysis and Applications
 | pages = 597–609
 | title = Triangulated graphs and the elimination process
 | volume = 32}}
*{{citation
 | last1 = Rose | first1 = D.
 | last2 = Lueker | first2 = George
 | last3 = Tarjan | first3 = Robert E. | author3-link = Robert E. Tarjan
 | doi = 10.1137/0205021
 | journal = [[SIAM Journal on Computing]]
 | mr = 0408312
 | pages = 266–283
 | title = Algorithmic aspects of vertex elimination on graphs
 | volume = 5
 | year = 1976
 | issue = 2}}.
*{{citation
 | last1 = Seymour | first1 = P. D. | author1-link = Paul Seymour (mathematician)
 | last2 = Weaver | first2 = R. W.
 | doi = 10.1002/jgt.3190080206
 | issue = 2
 | journal = [[Journal of Graph Theory]]
 | mr = 742878
 | pages = 241–251
 | title = A generalization of chordal graphs
 | volume = 8
 | year = 1984}}.
*{{citation
 | last1 = Szwarcfiter | first1 = J.L. | author1-link = Jayme Luiz Szwarcfiter 
 | last2 = Bornstein | first2 = C.F.
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | pages = 331–336
 | title = Clique graphs of chordal and path graphs
 | volume = 7
 | year = 1994 | issue = 2 | doi=10.1137/s0895480191223191| hdl = 11422/1497| hdl-access = free}}.

== External links ==
* [http://www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [http://www.graphclasses.org/classes/gc_32.html chordal graph]
*{{mathworld | urlname = ChordalGraph | title = Chordal Graph}}

[[Category:Graph families]]
[[Category:Perfect graphs]]
[[Category:Intersection classes of graphs]]