Macaulay2 » Documentation
Packages » Chordal :: ChordalGraph
next | previous | forward | backward | up | index | toc

ChordalGraph -- a chordal graph


This type represents a chordal graph G, together with a perfect elimination ordering.

An ordering of the vertices is a perfect elimination ordering if for each vertex $v$ the vertices $N(v)$ form a clique, where $N(v)$ consists of the adjacent nodes that occur after $v$ in the ordering. A graph is chordal if and only if it has a perfect elimination ordering. For notational convenience, ChordalGraph orients the edges of the graph according to such ordering.

The constructor of this type is chordalGraph. Chordal graphs can be visualized with displayGraph.

Several combinatorial problems can be solved efficiently on chordal graphs. In particular, chromaticNumber, cliqueNumber.

Functions and methods returning an object of class ChordalGraph :

Methods that use an object of class ChordalGraph :

For the programmer

The object ChordalGraph is a type, with ancestor classes Digraph < HashTable < Thing.