𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Detecting even holes

✍ Scribed by Maria Chudnovsky; Ken-ichi Kawarabayashi; Paul Seymour

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
220 KB
Volume
48
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Conforti, Cornue ´jols, Kapoor, and Vus ˇkovic ´(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,

📜 SIMILAR VOLUMES

Even and odd holes in cap-free graphs
Even and odd holes in cap-free graphs
✍ Conforti, Michele; Cornu�jols, G�rard; Kapoor, Ajai; Vu?kovi?, Kristina 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB 👁 1 views

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a g

Even-hole-free graphs part I: Decomposit
Even-hole-free graphs part I: Decomposition theorem
✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB

## Abstract We prove a decomposition theorem for even‐hole‐free graphs. The decompositions used are 2‐joins and star, double‐star and triple‐star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even‐hole‐free graphs. © 2002 John Wiley &

Even-hole-free graphs part II: Recogniti
Even-hole-free graphs part II: Recognition algorithm
✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 227 KB

## Abstract We present an algorithm that determines in polytime whether a graph contains an even hole. The algorithm is based on a decomposition theorem for even‐hole‐free graphs obtained in Part I of this work. We also give a polytime algorithm to find an even hole in a graph when one exists. © 20