Editing Chordal graph (section)

==Maximal cliques and graph coloring==
Another application of perfect elimination orderings is finding a maximum [[clique (graph theory)|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 clique]]s, while non-chordal graphs may have exponentially many. This implies that the class of chordal graphs has [[Graphs with few cliques|few cliques]]. To list all maximal cliques of a chordal graph, simply find a perfect elimination ordering, form a clique for each vertex {{mvar|v}} together with the neighbors of {{mvar|v}} that are later than {{mvar|v}} in the perfect elimination ordering, and test whether each of the resulting cliques is maximal.

The [[clique graph]]s of chordal graphs are the [[dually chordal graph]]s.{{sfnp|Szwarcfiter|Bornstein|1994}}

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 graph|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.{{sfnp|Maffray|2003}}

The [[chromatic polynomial]] of a chordal graph is easy to compute.  Find a perfect elimination ordering {{math|''v''{{sub|1}}, ''v''{{sub|2}}, …, ''v{{sub|n}}''}}.  Let {{mvar|N{{sub|i}}}} equal the number of neighbors of {{mvar|v{{sub|i}}}} that come after {{mvar|v{{sub|i}}}} in that ordering.  For instance, {{math|1=''N{{sub|n}}'' = 0}}.  The chromatic polynomial equals <math>(x-N_1)(x-N_2)\cdots(x-N_n).</math>  (The last factor is simply {{mvar|x}}, so {{mvar|x}} divides the polynomial, as it should.)  Clearly, this computation depends on chordality.<ref>For instance, {{harvtxt|Agnarsson|2003}}, Remark 2.5, calls this method well known.</ref>