set of all perfect elimination orderings of a chordal graph can be modeled as the basic words of an antimatroid; 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 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 cliques, while non-chordal graphs may have exponentially many. To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form a clique for each vertex together with the neighbors of that are later than in the perfect elimination ordering, and test whether each of the resulting cliques is maximal. The clique graphs of chordal graphs are the dually chordal graphs. 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: an optimal coloring may be obtained by applying a greedy coloring algorithm to the vertices in the reverse of a perfect elimination ordering. The chromatic polynomial of a chordal graph is easy to compute. Find a perfect elimination ordering . Let equal the number of neighbors of that come after in that ordering. For instance, . The chromatic polynomial equals (The last factor is simply , so divides the polynomial, as it should.) Clearly, this computation depends on chordality. 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 , chordal graphs are graphs in which each minimal separator is a clique; Dirac used this characterization to prove that chordal graphs are perfect. The family of chordal graphs may be defined inductively as the graphs whose vertices can be divided into three nonempty subsets , , and , such that and both form chordal induced subgraphs, is a clique, and there are no edges from to . 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. Intersection graphs