next | previous | forward | backward | up | index | toc

# allOddHoles -- returns all odd holes in a graph

## Synopsis

• Usage:
L = allOddHoles G
• Inputs:
• G, ,
• Outputs:
• L, a list, returns all odd holes contained in G.

## 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 : allOddHoles G --only the 5-cycle should appear o3 = {{x , x , x , x , x }} 1 2 3 4 5 o3 : List 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 : allOddHoles H o5 = {} o5 : List