Chordal graph

From Free net encyclopedia

Image:Chordal-graph.svg In graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that induced subgraphs that are simple cycles have at most three nodes. Chordal graphs are a subset of the perfect graphs.

Chordality of a graph is equivalent to the condition that every node and all nodes connected to it and preceding it in a max-cardinality ordering form a clique. A max-cardinality ordering can be produced by arbitrarily choosing the least node, and then iteratively choosing the <math>i</math>-th node among the ones connected to a maximal number of nodes between the first and the <math>i-1</math>-th.

Since producing a max-cardinality ordering and checking the condition on the cliques can be both done in polynomial time, establishing chordality can be checked in polynomial time.

Another application of the equivalent condition to chordality is that finding the maximal cliques of a chordal graph is a polynomial-time problem, while the same problem is NP-complete on general graphs. These maximal cliques can indeed be found by the fact that every clique is composed by a node and all nodes connected to it and preceding it in the max-cardinality ordering.