isPerfect -- determines whether a graph is perfect

Synopsis

• Usage:
b = isPerfect G
• Inputs:
• G, ,
• Outputs:
• b, , 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