Editing Chordal graph (section)

{{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.