Macaulay2 » Documentation
Packages » EdgeIdeals :: isPerfect
next | previous | forward | backward | up | index | toc

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.