𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some properties of minimal imperfect graphs

✍ Scribed by Chính T. Hoàng

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
539 KB
Volume
160
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The connectivity of minimal imperfect gr
The connectivity of minimal imperfect graphs
✍ Seb�, Andr�s 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

We prove that partitionable graphs are 2w -2-connected, that this bound is sharp, and prove some structural properties of cutsets of cardinality 2w -2. The proof of the connectivity result is a simple linear algebraic proof.

A classification of certain graphs with
A classification of certain graphs with minimal imperfection properties
✍ S.H. Whitesides 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 941 KB

IfI,: family of Bar, w) graphs ate of interest for several reasons. For example, any minimal fomenter-example to Rerge's Strong Perfect Graph Conjecture t %ngs to this family. This paper aciounts for ail (4.3) graphs. One of these is not obtainatde by existing techniques for geg~~rati~g (a + I, w) g

On minimal imperfect graphs with circula
On minimal imperfect graphs with circular symmetry
✍ Bacs�, G�bor; Boros, Endre; Gurvich, Vladimir; Maffray, Fr�d�ric; Preissmann, My 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 293 KB

Results of Lovász and Padberg entail that the class of so-called partitionable graphs contains all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture, which asserts that the only minimal imperfect graphs are the odd chordless cycles with at least five vertices (''odd hol

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

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

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