×

Slim graphs. (English) Zbl 0677.05065

The author investigates Slim graphs which can be obtained by deleting in a Meyniel graph G all the edges induced by an arbitrary set of nodes. Besides proving that Slim graphs are perfect a simple proof of the conjecture is given that Meyniel graphs are locally perfect graphs.
Reviewer: Ch.Meinel

MSC:

05C75 Structural characterization of families of graphs
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, C.: Färbung von Graphen, deren sämtliche bzw. deren ungerade Kreise starr sind. Wissenschaftliche Zeitschrift, Martin-Luther-Univ. Halle-Wittenberg10, 114–115 (1961)
[2] Berge, C.: Graphes. Paris: Gauthier-Villars 1983
[3] Berge, C. Duchet, P.: Strongly perfect graphs. In: Topics on Perfect Graphs, edited by C. Berge, V. Chvátal Ann. Discrete Math.21, 57–61 (1984) · Zbl 0558.05037
[4] Chvátal, V.: Star Cutset and Perfect Graphs, J. Comb. Theory (B)39, 189–199 (1985) · Zbl 0674.05058 · doi:10.1016/0095-8956(85)90049-8
[5] Hoàng, C.T.: On a conjecture of Meyniel, J. Comb. Theory (B)42, 302–312 (1987) · Zbl 0634.05058 · doi:10.1016/0095-8956(87)90047-5
[6] Lovász, L.: Normal hypergraphs and the Weak Perfect Graph Conjecture. In: Topics on Perfect Graphs, edited by C. Berge, V. Chvátal. Ann. Discrete Math.21, 29–42 (1984)
[7] Meyniel, H.: A new property of critical imperfect graphs and some consequences. Europ. J. Comb.8, 313–316 (1987) · Zbl 0647.05053
[8] Meyniel, H.: On the perfect graph conjecture, Discrete Math16, 339–342 (1976) · Zbl 0383.05018 · doi:10.1016/S0012-365X(76)80008-8
[9] Preissmann, M.: Locally perfect graphs (submitted for publication in J. Comb. Theory (B)). · Zbl 0649.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.