Perfect elimination ordering
Order vertices s.t. each vertex's later neighbors form clique. Testable in O(V+E) via LexBFS.
Advertisement
Max clique
Polynomial (NP-hard general). At each vertex in reverse elimination order, check clique of vertex + later neighbors.
Advertisement
Coloring
Greedy in reverse elimination order gives optimal coloring. χ = ω (chromatic = clique number). Perfect graph.
Tree decomposition
Chordal graphs = graphs with tree decomposition where every bag is a clique. Foundation of parameterized algorithms.