zbMATH — the first resource for mathematics

Star-cutsets and perfect graphs. (English) Zbl 0674.05058
This paper presents a general structure for understanding various known techniques for producing a new perfect graph \(G^*\) out of a given pair of old perfect graphs \(G_ 1,G_ 2\). A common property of these techniques is that: if an induced subgraph F of \(G^*\) (with F having at least three vertices) is an induced subgraph of neither \(G_ 1\) nor \(G_ 2\), then F has a star-cutset or its complement \(F^ c\) is disconnected. Here a star-cutset is a set of vertices that form a cutset and whose induced subgraph contains some vertex adjacent to all others in the cutset. The star closure \({\mathcal C}^*\) of a class \({\mathcal C}\) of graphs is recursively defined by the rules: (i) if \(G\in {\mathcal C}\), then \(G\in {\mathcal C}^*\); and (ii) if G or \(G^ c\) has a star-cutset and if G-v\(\in {\mathcal C}^*\) for all v in G, then \(G\in {\mathcal C}^*\). The author proves that two classes of strongly perfect graphs, the Meyniel graphs and perfectly orderable graphs, are in the star closure of the class of bipartite graphs.

05C99 Graph theory
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Berge, C, ()
[2] Berge, C; Duchet, P, Strongly perfect graphs, (), 57-61 · Zbl 0558.05037
[3] Bixby, R.E, A composition for perfect graphs, (), 221-224
[4] Bland, R.G; Huang, H.-C; Trotter, L.E, Graphical properties related to minimal imperfection, Discrete math., 27, 11-22, (1979) · Zbl 0421.05028
[5] Burlet, M; Fonlupt, J, Polynomial algorithm to recognize a meyniel graph, (), 225-252 · Zbl 0558.05055
[6] Chvátal, V, Perfectly ordered graphs, (), 63-65 · Zbl 0559.05055
[7] Chvátal, V; Graham, R.L; Perold, A.F; Whitesides, S.H, Combinatorial designs related to the strong perfect graph conjecture, Discrete math., 26, 83-92, (1979) · Zbl 0403.05017
[8] Cornuéjols, G; Cunningham, W.H, Compositions for perfect graphs, Discrete math., 55, 245-254, (1985) · Zbl 0562.05043
[9] {\scR. B. Hayward}, Weakly triangulated graphs, Montreux; Technical Report 83.22, School of Computer Science, McGill University, J. Combin. Theory Ser. B, in press. · Zbl 0837.05075
[10] {\scW.-L. Hsu}, Decompositions of perfect graphs, a manuscript.
[11] Lovász, L, Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[12] Meyniel, H, On the perfect graph conjecture, Discrete math., 16, 339-342, (1976) · Zbl 0383.05018
[13] Olaru, E; Olaru, E; Sachs, H, Contributions to a characterization of the structure of perfect graphs, (), 15, 121-144, (1969), See also
[14] Ravindra, G, Meyniel graphs are strongly perfect, J. combin. theory ser. B, 33, 187-190, (1982) · Zbl 0498.05055
[15] Seymour, P.D, Decomposition of regular matroids, J. combin. theory ser. B, 28, 305-359, (1980) · Zbl 0443.05027
[16] Tucker, A, Critical perfect graphs and perfect 3-chromatic graphs, J. combin. theory ser. B, 23, 143-149, (1977) · Zbl 0376.05047
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.