×

Slightly triangulated graphs are perfect. (English) Zbl 0814.05035

A graph \(G\) is said to be slightly triangulated iff \(G\) has the following two properties: (i) \(G\) contains no chordless cycle with at least 5 vertices, and (ii) for every induced subgraph \(H\) of \(G\), there is a vertex in \(H\) the neighbourhood of which in \(H\) contains no chordless path of 4 vertices. The author shows that every slightly triangulated graph is perfect. Comparisons with other classes of perfect graphs and open problems are considered too.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berge, Sur une conjecture relative au probleme des codes optimaux, Commun. 13 eme Assemblee Gen. URSI, Tokyo, 1962
[2] Berge, C., Chvátal, V.: Topics on perfect graphs, Ann. Discrete Math.21, (1984) · Zbl 0546.00006
[3] Berge, C.; Duchet, P.; Berge, C.; Chvátal, V., strongly perfect graphs, in “Topics on perfect graphs”, 57-61 (1984), Amsterdam: North-Holland, Amsterdam · Zbl 0558.05037 · doi:10.1016/S0304-0208(08)72922-0
[4] Bland, R. G.; Huang, H. C.; Trotter, L. E.; Berge, C.; Chvátal, V., Graphical properties related to minimal imperfection, in “Topics on perfect graphs”, 181-192 (1984), Amsterdam: North-Holland, Amsterdam · Zbl 0556.05030
[5] Chvátal, V.; Graham, R. L.; Perold, A. F.; Whitesides, S. H.; Berge, C.; Chvátal, V., Combinatorial designs related to the perfect graph conjecture, in “Topics on perfect graphs”, 197-206 (1984), Amsterdam: North-Holland, Amsterdam · Zbl 0556.05012
[6] Chvátal, V.; Berge, C.; Chvátal, V., Perfectly Ordered Graphs, “Topics on perfect graphs”, 63-65 (1984), Amsterdam: North-Holland, Amsterdam · Zbl 0559.05055 · doi:10.1016/S0304-0208(08)72923-2
[7] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), New York: Academic Press, New York · Zbl 0541.05054
[8] Hayward, R., Weakly triangulated graphs, J. Comb. Theory (B), 39, 200-208 (1985) · Zbl 0551.05055 · doi:10.1016/0095-8956(85)90050-4
[9] Hayward, R.; Hoàng, C.; Maffray, F., Optimizing weakly triangulated graphs, Graphs and Combinatorics, 5, 339-349 (1989) · Zbl 0679.68082 · doi:10.1007/BF01788689
[10] Lubiw, A., Short-chorded and perfect graphs, J. Comb. Theory (B), 39, 24-33 (1991) · Zbl 0755.05072 · doi:10.1016/0095-8956(91)90003-3
[11] Maire, F.: Des polyominus aux graphes parfaits, PhD Thesis University Paris 6, June 1993
[12] Maire, F., A characterization of intersection graphs of the maximal rectangles of a polyomino, Discrete Maths, 120, 211-214 (1993) · Zbl 0793.05049 · doi:10.1016/0012-365X(93)90578-H
[13] Meyniel, H.; Berge, C.; Chvátal, V., The graphs whose odd cycles have at leat two chords, “Topics on perfect graphs”, 115-119 (1984), Amsterdam: North-Holland, Amsterdam · Zbl 0567.05034 · doi:10.1016/S0304-0208(08)72927-X
[14] Padberg, M., “Perfect zero-one matrices”, Math. Programming, 6, 180-196 (1974) · Zbl 0284.90061 · doi:10.1007/BF01580235
[15] Seinsche, D., On a property of the class ofn-colorable graphs, J. Comb. Theory (B), 16, 191-193 (1974) · Zbl 0269.05103 · doi:10.1016/0095-8956(74)90063-X
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.