✦ LIBER ✦

No odd pairs in minimal imperfect NP5 graphs

✍ Scribed by Jean-Luc Fouquet

Book ID: 104136739
Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 55 KB
Volume: 83
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00329-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

No antitwins in minimal imperfect graphs

✍ Stephan Olariu 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 132 KB

On minimal cutsets in P5-free minimal im

On minimal cutsets in P5-free minimal imperfect graphs

✍ Vincent Barré; Jean-Luc Fouquet 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 115 KB

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 Sebo&#x030B; 📂 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

About Skew Partitions in Minimal Imperfe

About Skew Partitions in Minimal Imperfect Graphs

✍ F. Roussel; P. Rubio 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 188 KB

V. Chva tal conjectured in 1985 that a minimal imperfect graph G cannot have a skew cutset (i.e., a cutset S decomposable into disjoint sets A and B joined by all possible edges). We prove here the conjecture in the particular case where at least one of A and B is a stable set. 2001 Elsevier Science

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