Chordality Check

A graph is chordal when every cycle of four or more vertices has a chord, an edge connecting two non-consecutive vertices of the cycle. Chordal graphs are a well-behaved class where many NP-hard problems, including coloring and maximum clique, become solvable in polynomial time.

How it works

Chordality is tested with Lexicographic BFS (Lex-BFS), which orders the vertices in O(V + E) time. A graph is chordal exactly when the reverse of this order is a perfect elimination ordering, meaning each vertex together with its later neighbors forms a clique, a condition checked in linear time. The same ordering then yields optimal coloring and maximum cliques greedily.

Applications

Chordal graphs enable efficient Gaussian elimination with minimal fill-in for sparse matrices, exact inference in probabilistic graphical models through junction trees, perfect phylogeny in computational biology, and register allocation for structured programs. They are a gateway topic into perfect graph theory.