✦ LIBER ✦

About Skew Partitions in Minimal Imperfect Graphs

✍ Scribed by F. Roussel; P. Rubio

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 188 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2044

No coin nor oath required. For personal study only.

✦ Synopsis

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 :(H) } |(H) |H|. This theorem was the first step towards a new approach of minimal imperfect graphs. The results of Padberg [11], Tucker [12], and Lova sz

📜 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