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.

The IsComparabilityGraph(G) command returns true if G is a comparability graph and false otherwise.

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.

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

$\mathrm{C4}≔\mathrm{CycleGraph}\left(4\right)$

$\mathrm{C4}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 4\; vertices\; and\; 4\; edge(s)}$

$\mathrm{IsComparabilityGraph}\left(\mathrm{C4}\right)$

$\mathrm{true}$

$\mathrm{C5}≔\mathrm{CycleGraph}\left(5\right)$

$\mathrm{C5}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 5\; vertices\; and\; 5\; edge(s)}$

$\mathrm{IsComparabilityGraph}\left(\mathrm{C5}\right)$

$\mathrm{false}$

$\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(s)}$

$G≔\mathrm{GraphComplement}\left(\mathrm{IG}\right)$

$G≔\mathrm{Graph\; 4:\; an\; undirected\; graph\; with\; 9\; vertices\; and\; 12\; edge(s)}$

$\mathrm{IsComparabilityGraph}\left(G\right)$

$\mathrm{true}$

$P≔\mathrm{SpecialGraphs}:-\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 5:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{IsComparabilityGraph}\left(P\right)$

$\mathrm{false}$

The GraphTheory[IsComparabilityGraph] command was introduced in Maple 2022.

For more information on Maple 2022 changes, see Updates in Maple 2022.