### Abstract

Conforti, Cornuéjols, Kapoor, and Vušković (Even-hole-free graphs. Part II: Recognition algorithm, J Graph Theory 40 (2002), 238-266) gave a 73-page polynomial time algorithm to test whether a graph has an induced subgraph that is a cycle of even length. Here, we provide, another algorithm to solve the same problem. The differences are: (1) our algorithm is simpler - we are able to search directly for even holes, while the algorithm of Conforti et al. made use of a structure theorem for even-hole-free graphs, proved in an earlier paper (Conforti, Cornuéjols, Kapoor, and Vušković, Even-hole-free graphs: Part I: Decomposition theorem, J Graph Theory 39 (2002), 6-49); (2) our algorithm is marginally faster - O(n ^{31}) for an n-vertex graph (and we sketch another more complicated algorithm that runs in time 0(n^{15})) while the earlier algorithm appears to take about 0(n^{40}); and (3) we can permit 0/1 weights on the edges and look for an induced cycle of even weight. Consequently, we can test whether a graph is "odd Signable."

Original language | English (US) |
---|---|

Pages (from-to) | 85-111 |

Number of pages | 27 |

Journal | Journal of Graph Theory |

Volume | 48 |

Issue number | 2 |

DOIs | |

State | Published - Feb 2005 |

### All Science Journal Classification (ASJC) codes

- Geometry and Topology

### Keywords

- Even hole
- Recognition algorithm
- Signed graph

## Fingerprint Dive into the research topics of 'Detecting even holes'. Together they form a unique fingerprint.

## Cite this

*Journal of Graph Theory*,

*48*(2), 85-111. https://doi.org/10.1002/jgt.20040