New classes of Berge perfect graphs (Q1332433)

From MaRDI portal
scientific article
Language Label Description Also known as
English
New classes of Berge perfect graphs
scientific article

    Statements

    New classes of Berge perfect graphs (English)
    0 references
    0 references
    0 references
    28 February 1995
    0 references
    Chvátal proved the star-cutset lemma saying that no maximal imperfect graph has a star-cutset. Using a notion of reducible clique and a special type of derived graph \(G| K\) (for a set \(K\subset V)\), \textit{A. Sassano} [Reducible cliques and the strong perfect graph conjecture, IASI Tech. Report R 257 (1989)] proved the following: If \(\mathcal G\) is a hereditary class of Berge graphs in which each minimal imperfect graph \(G\) has a reducible clique \(K\) of size \(\omega(G)\) such that \(G| K\) is also in \(\mathcal G\), then every graph in \(\mathcal G\) is perfect. In this paper, the authors prove that if \(e\) is an edge not belonging to any triangle of a minimal imperfect Berge graph \(G\), then \(G-e\) is also a minimal imperfect Berge graph. The authors prove four classes of Berge graphs to be perfect: The chair is a graph with vertices \(a\), \(b\), \(c\), \(d\), \(e\) and edges \(ab\), \(bc\), \(cd\), \(be\). The graph \(F_ 2\) is obtained from a triangle by attaching a \(P_ 2\) at one vertex and a \(P_ 3\) at another vertex (or has vertices \(a\), \(b\), \(c\), \(d\), \(e\), \(f\) and edges \(ab\), \(bc\), \(ca\), \(ad\), \(be\), \(ef\)). \(G_ 0\) is the graph \(P_ 4\cup K_ 1\) and \(G_ 1\) is obtained from a diamond by attaching a pendant edge at a vertex of degree 2. \(H\) is the graph \(C_ 4\cup K_ 1\). Result 1: Every chair-free and \(F_ 2\)-free Berge graph is perfect. Result 2: Every \(P_ 5\)-free and \(K_{2,3}\)-free Berge graph is perfect. Result 4: Every \(G_ 0\)-free and \(G_ 1\)-free Berge graph is perfect. Result 5: Every \(\overline C_ 4\)-free and \(H\)-free Berge graph is perfect. The first two are proved using the star-cutset lemma, the third using Sassano's result and the fourth using the authors' result quoted above. All but one of the above classes of graphs are \(\overline C_ 4\)-free. Thus considerable progress is achieved towards proving \(\overline C_ 4\)-free Berge graphs to be perfect.
    0 references
    perfect graphs
    0 references
    star-cutset lemma
    0 references
    imperfect graph
    0 references
    reducible clique
    0 references
    Berge graphs
    0 references
    chair
    0 references

    Identifiers