next | previous | forward | backward | up | index | toc

# ChordalGraph -- a chordal graph

## Description

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 :

• chordalGraph(Digraph) -- see chordalGraph -- chordal completion of a graph
• chordalGraph(Graph) -- see chordalGraph -- chordal completion of a graph
• chordalGraph(Graph,List) -- see chordalGraph -- chordal completion of a graph
• chordalGraph(ElimTree) -- see ElimTree -- the elimination tree of a chordal graph

## Methods that use an object of class ChordalGraph :

• chromaticNumber(ChordalGraph)
• cliqueNumber(ChordalGraph)
• inducedSubgraph(ChordalGraph)
• isChordal(ChordalGraph)
• isPerfect(ChordalGraph)
• net(ChordalGraph)
• elimTree(ChordalGraph) -- see elimTree -- elimination tree of a chordal graph
• treewidth(ChordalGraph) -- see treewidth -- treewidth of a graph

## For the programmer

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