𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Even-hole-free graphs part II: Recognition algorithm

✍ Scribed by Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković

Publisher
John Wiley and Sons
Year
2002
Tongue
English
Weight
227 KB
Volume
40
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 238–266, 2002

📜 SIMILAR VOLUMES

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 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

K4-free graphs with no odd hole: Even pa
K4-free graphs with no odd hole: Even pairs and the circular chromatic number
✍ Yori Zwols 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K 4 -free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K 4 -free graph with no odd hole has