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

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.

See C.A. Francisco, H.T. Ha, A. Van Tuyl, "Algebraic methods for detecting odd holes in a graph." (2008) Preprint. arXiv:0806.1159v1.

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 :

For the programmer

The object hasOddHole is a method function.