next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Posets :: isComparabilityGraph

isComparabilityGraph -- determines if a graph is the comparability graph of a poset

Synopsis

Description

A Graph (missing documentation) G is a comparabilityGraph of a poset if it is has a transitiveOrientation.
i1 : G = comparabilityGraph booleanLattice 5;
i2 : isComparabilityGraph G

o2 = true
However, a non-triangular odd cycle is never a comparability graph.
i3 : G = graph {{1,2}, {2,3}, {3,4}, {4,5}, {1,5}};
i4 : isComparabilityGraph G

o4 = false
This method calls transitiveOrientation and checks that an error is not thrown. See the documentation for that method for a note on the implemented algorithm.

See also

Ways to use isComparabilityGraph :