isPerfect -- determines whether a graph is perfect

Synopsis

Usage:
b = isPerfect G
Inputs:
- G, a graph
Outputs:
- b, a Boolean value, true if G is perfect and false otherwise

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

Ways to use `isPerfect` :

isPerfect(Graph)

isPerfect -- determines whether a graph is perfect

Synopsis

Description

See also

Ways to use isPerfect :

Ways to use `isPerfect` :