✦ LIBER ✦

Complete Multi-partite Cutsets in Minimal Imperfect Graphs

✍ Scribed by G. Cornuejols; B. Reed

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 316 KB
Volume: 59
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1993.1065

No coin nor oath required. For personal study only.

✦ Synopsis

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 holes. It is also a special case of a conjecture of Chvátal. 1993 Academic Press, Inc.

📜 SIMILAR VOLUMES

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 the asymptotic value of the choice nu

On the asymptotic value of the choice number of complete multi-partite graphs

✍ Nurit Gazit; Michael Krivelevich 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We calculate the asymptotic value of the choice number of complete multi‐partite graphs, given certain limitations on the relation between the sizes of the different sides. In the bipartite case, we prove that if __n__~0~ ≤ __n__~1~ and log__n__~0~ ≫ loglog__n__~1~, then $ch(K\_{n\_{0},