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

GraphTheory

 IsComparabilityGraph
 test if graph is a comparability graph

 Calling Sequence IsComparabilityGraph(G,opts)

Parameters

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

Options

 • transitiveorientation : keyword option of the form transitiveorientation=true or transitiveorientation=false.
 Specifies whether a directed graph representing a transitive orientation of G should be returned when G is a comparability graph. 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 IsComparabilityGraph(G) command returns true if G is a comparability graph and false otherwise.

Definition

 • An undirected graph G is a comparability graph if it has a transitive orientation; that is, there exists a corresponding directed graph G2 with an identical vertex set and exactly one directed edge for each edge of G, and which also has the property that whenever there are directed edges from u to v and from v to w, there is also a directed edge from u to w.
 • The complement of a comparability graph is an interval graph.

Examples

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

The cycle graph on an even number of vertices is a comparability graph.

 > $\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{IsComparabilityGraph}\left(\mathrm{C4}\right)$
 ${\mathrm{true}}$ (2)

The cycle graph on an odd number of vertices is not a comparability graph.

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

The complement of an interval graph is a comparability graph.

 > $\mathrm{IG}≔\mathrm{IntervalGraph}\left(\left[1..4,2..3,2..6,3..7,4..9,5..8,6..9,7..9,8..10\right]\right)$
 ${\mathrm{IG}}{≔}{\mathrm{Graph 3: an undirected graph with 9 vertices and 24 edge\left(s\right)}}$ (5)
 > $G≔\mathrm{GraphComplement}\left(\mathrm{IG}\right)$
 ${G}{≔}{\mathrm{Graph 4: an undirected graph with 9 vertices and 12 edge\left(s\right)}}$ (6)
 > $\mathrm{IsComparabilityGraph}\left(G\right)$
 ${\mathrm{true}}$ (7)

The Petersen graph is not a comparability graph.

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

Compatibility

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