✦ LIBER ✦

Detecting Holes and Antiholes in Graphs

✍ Scribed by Stavros D. Nikolopoulos; Leonidas Palios

Publisher: Springer
Year: 2007
Tongue: English
Weight: 227 KB
Volume: 47
Category: Article
ISSN: 0178-4617
DOI: 10.1007/s00453-006-1225-y

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Detecting even holes

✍ Maria Chudnovsky; Ken-ichi Kawarabayashi; Paul Seymour 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB

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 so

Holes in random graphs

✍ Tomasz Łuczak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 376 KB

Balanced cycles and holes in bipartite g

Balanced cycles and holes in bipartite graphs

✍ Michele Conforti; Gérard Cornuéjols; Kristina Vušković 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 414 KB

Bruce Reed asks the following question: Can we determine whether a bipartite graph contains a chordless cycle whose length is a multiple of 4? We show that the two following more general questions are equivalent and we provide an answer. Given a bipartite graph G where each edge is assigned a weight

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

Disjoint clique cutsets in graphs withou

Disjoint clique cutsets in graphs without long holes

✍ Elaine M. Eschen; Chính T. Hoàng; Mark D. T. Petrick; R. Sritharan 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB

## Abstract A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class

Chordless Paths, Odd Holes, and Kernels

Chordless Paths, Odd Holes, and Kernels in Graphs Without m-Obstructions

✍ F. Gavril; V.T. Laredo; D. Dewerra 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 689 KB

An \(m\)-obstruction in a directed graph \(\mathbf{G}(V, \mathbf{E})\) is a chordless simple path \(x_{1}, x_{2}, \ldots, x_{m+2}\) having \(x_{1} \rightarrow x_{2}, x_{m+2} \rightarrow x_{m+1} \in \mathbf{E}\). A directed graph is fraternally oriented if it has no 1 -obstructions and it is perfectl