𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On minimally b-imperfect graphs

✍ Scribed by Chính T. Hoàng; Cláudia Linhares Sales; Frédéric Maffray

Book ID
108112810
Publisher
Elsevier Science
Year
2009
Tongue
English
Weight
979 KB
Volume
157
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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