IsChordal - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

GraphTheory

 IsChordal
 test if graph is chordal

 Calling Sequence IsChordal(G,opts)

Parameters

 G - graph opts - (optional) one or more options as specified below

Options

 • eliminationordering : keyword option of the form eliminationordering=true or eliminationordering=false.
 Specifies whether an elimination ordering should be returned when G is chordal. The default is false.
 • usecached : keyword option of the form usecached=true or usecached=false.
 Specifies whether previously stored information should be used, if available. The default is true.

Description

 • The IsChordal(G) command returns true if G is a chordal graph and false otherwise.

Definition

 • An undirected graph G is chordal if every cycle of length 4 or more has a chord, that is, an edge that is not part of the cycle but connects two vertices of the cycle.
 • Every interval graph is a chordal graph.
 • Every split graph is a chordal graph.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

The cycle graph on four vertices is not chordal by definition, since it is a 4-cycle without a chord.

 > $\mathrm{C4}≔\mathrm{CycleGraph}\left(4\right)$
 ${\mathrm{C4}}{≔}{\mathrm{Graph 1: an undirected graph with 4 vertices and 4 edge\left(s\right)}}$ (1)
 > $\mathrm{IsChordal}\left(\mathrm{C4}\right)$
 ${\mathrm{false}}$ (2)

The complete graph on four vertices is chordal.

 > $\mathrm{K4}≔\mathrm{CompleteGraph}\left(4\right)$
 ${\mathrm{K4}}{≔}{\mathrm{Graph 2: an undirected graph with 4 vertices and 6 edge\left(s\right)}}$ (3)
 > $\mathrm{IsChordal}\left(\mathrm{K4}\right)$
 ${\mathrm{true}}$ (4)

The Petersen graph is not chordal.

 > $P≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$
 ${P}{≔}{\mathrm{Graph 3: an undirected graph with 10 vertices and 15 edge\left(s\right)}}$ (5)
 > $\mathrm{IsChordal}\left(P\right)$
 ${\mathrm{false}}$ (6)

Compatibility

 • The GraphTheory[IsChordal] command was introduced in Maple 2022.
 • For more information on Maple 2022 changes, see Updates in Maple 2022.