chordal

Chordal, in graph theory, refers to chordal graphs, also called triangulated graphs. A graph is chordal if every cycle of length four or more has a chord, an edge connecting two nonconsecutive vertices of the cycle. This property forbids induced cycles longer than three and underpins several useful characterizations.

One equivalent definition uses a perfect elimination ordering (PEO): an ordering of the vertices such that, for each vertex, the neighbors that come later in the order form a clique. A graph is chordal if and only if it admits a PEO. This perspective links chordality to sparse matrix factorization and to dynamic programming on tree-like decompositions.

Key properties include: the clique number ω(G) and the graph’s treewidth are tightly related, with treewidth equal to ω(G) − 1 for chordal graphs. Chordal graphs are also perfect, meaning in every induced subgraph the chromatic number equals the clique number, which implies that many coloring and clique problems are tractable on this class.

Recognition and algorithms: chordality can be tested in linear time using Maximum Cardinality Search (MCS) or Lexicographic Breadth-First Search (LexBFS). Once chordal, problems such as finding a maximum clique, an optimal vertex coloring, or performing certain decompositions can be solved efficiently, often by following a PEO.

Examples and relatives: trees, forests, complete graphs, and interval graphs are chordal. Cycles of length four or more without chords are not chordal. Chordal graphs play a prominent role in applications like sparse matrix factorization, database query optimization, and probabilistic graphical models, where chordal structure enables efficient inference via junction trees.