IsPerfectGraph - Maple Help

GraphTheory

 IsPerfectGraph
 test if graph is perfect

 Calling Sequence IsPerfectGraph(G,opts)

Parameters

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

Options

 • 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 IsPerfectGraph(G) command returns true if G is a perfect graph and false otherwise.

Definition

 • An undirected graph G is perfect if in every subgraph of G, the chromatic number is equal to the clique number.
 • Split graphs are closed under graph complement.
 • Every chordal graph is a perfect graph.
 • Every split graph is a perfect graph.

Examples

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

The cycle graph on four vertices is not perfect.

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

The complete graph on four vertices is perfect.

 > $\mathrm{K5}≔\mathrm{CompleteGraph}\left(5\right)$
 ${\mathrm{K5}}{≔}{\mathrm{Graph 2: an undirected graph with 5 vertices and 10 edge\left(s\right)}}$ (3)
 > $\mathrm{IsPerfectGraph}\left(\mathrm{K5}\right)$
 ${\mathrm{true}}$ (4)

The Petersen graph is not perfect.

 > $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{IsPerfectGraph}\left(P\right)$
 ${\mathrm{false}}$ (6)

Compatibility

 • The GraphTheory[IsPerfectGraph] command was introduced in Maple 2022.