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

# allOddHoles -- returns all odd holes in a graph

- Usage:
    `L = allOddHoles G`
- Inputs:
  - G, a graph,
- 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

## See also

- allEvenHoles -- returns all even holes in a graph
- hasOddHole -- tells whether a graph contains an odd hole

## Ways to use allOddHoles:

- `allOddHoles(Graph)`

## For the programmer

The object allOddHoles is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/EdgeIdeals.m2:1821:0.