next | previous | forward | backward | up | top | index | toc | Macaulay2 website
EdgeIdeals :: isPerfect

isPerfect -- determines whether a graph is perfect

Synopsis

Description

The algorithm uses the Strong Perfect Graph Theorem, which says that G is perfect if and only if neither G nor its complement contains an odd hole. hasOddHole is used to determine whether these conditions hold.

i1 : R = QQ[x_1..x_7];
i2 : G = complementGraph cycle R; --odd antihole with 7 vertices
i3 : isPerfect G

o3 = false
i4 : H = cycle(R,4)

o4 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }}}
                       1   2     2   3     3   4     1   4
           ring => R
           vertices => {x , x , x , x , x , x , x }
                         1   2   3   4   5   6   7

o4 : Graph
i5 : isPerfect H

o5 = true

See also

Ways to use isPerfect :

For the programmer

The object isPerfect is a method function.