Chordal graph

Chordal graph — хордальный граф.

A graph that does not contain chordless cycles of length greater than three is called a chordal graph. This is equivalent to saying that the graph does not contain an induced subgraph isomorphic to [math]\displaystyle{ \,C_{n} }[/math] (i.e., a cycle of length [math]\displaystyle{ \,n }[/math]) for [math]\displaystyle{ \,n \gt 3 }[/math].

There are many ways to characterize chordal graphs. Although many of these characterizations are interesting and useful, it suffices to list only some of them. One of the most important tools is the concept of a perfect elimination scheme. The other way to define a chordal graph is to consider it as an intersection graph of a family of subtrees of a tree.

An important subclass of chordal graphs is the interval graphs.

Other names of a chordal graph are Triangulated graph, Rigid circuit graph, Perfect elimination graph, Monotone transitive graph.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.