next | previous | forward | backward | up | top | index | toc | directory | Macaulay 2 web site

hasOddHole -- tells whether a graph contains an odd hole.

Synopsis

Description

An odd hole is an odd induced cycle of length at least 5. The method is based on work of Francisco-Ha-Van Tuyl, looking at the associated primes of the square of the Alexander dual of the edge ideal.
i1 : R = QQ[x_1..x_6];
i2 : G = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6}) --5-cycle and a triangle

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

o2 : Graph
i3 : hasOddHole G

o3 = true
i4 : H = graph({x_1*x_2,x_2*x_3,x_3*x_4,x_4*x_5,x_1*x_5,x_1*x_6,x_5*x_6,x_1*x_4}) --no odd holes

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

o4 : Graph
i5 : hasOddHole H

o5 = false

See also

Ways to use hasOddHole :