𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On transversals in minimal imperfect graphs

✍ Scribed by Jean-Luc Fouquet; Frédéric Maire; Irena Rusu; Henri Thuillier

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
885 KB
Volume
165-166
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 strong as Berge's strong perfect graph conjecture for a very large class of graphs, namely for those graphs whose diameter does not exceed 6.

📜 SIMILAR VOLUMES

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 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

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.