𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On minimal cutsets in P5-free minimal imperfect graphs

✍ Scribed by Vincent Barré; Jean-Luc Fouquet

Book ID
108315605
Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
115 KB
Volume
236
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Complete Multi-partite Cutsets in Minima
Complete Multi-partite Cutsets in Minimal Imperfect Graphs
✍ G. Cornuejols; B. Reed 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 316 KB

We show that a minimal imperfect graph \(G\) cannot contain a cutset \(C\) which induces a complete multi-partite graph unless \(C\) is a stable set and \(G\) is an odd hole. This generalizes a result of Tucker, who proved that the only minimal imperfect graphs containing stable cutsets are the odd

On transversals in minimal imperfect gra
On transversals in minimal imperfect graphs
✍ Jean-Luc Fouquet; Frédéric Maire; Irena Rusu; Henri Thuillier 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 885 KB

proved that no minimal imperfect graph has a small transversal, that is, a set of vertices of cardinality at most x + M-1 which meets every c+clique and every x-stable set. In this paper we prove that a slight generalization of this notion of small transversal leads to a conjecture which is as stro

On Critical Edges in Minimal Imperfect G
On Critical Edges in Minimal Imperfect Graphs
✍ András Sebő 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 725 KB

An edge of a graph is called critical, if deleting it the stability number of the graph increases, and a nonedge is called co-critical, if adding it to the graph the size of the maximum clique increases. We prove in this paper, that the minimal imperfect graphs containing certain configurations of t

On minimal 5-chromatic triangle-free gra
On minimal 5-chromatic triangle-free graphs
✍ David Avis 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract It is shown that the minimum number of vertices in a triangle‐free 5‐chromatic graph is at least 19.