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

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



A Graph $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 :

For the programmer

The object isComparabilityGraph is a method function.