Two classes of perfect graphs (Q1112847)

From MaRDI portal
Revision as of 14:29, 15 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Two classes of perfect graphs
scientific article

    Statements

    Two classes of perfect graphs (English)
    0 references
    1991
    0 references
    Claude Berge proposed to call a graph perfect if, for each of its induced subgraph \(F\), the chromatic number of \(F\) equals the largest number of pairwise adjacent vertices in \(F\). An odd hole is a chordless cycle whose number of vertices is odd and at least five. Berge conjectured that a graph is perfect if and only if none of its induced subgraphs is an odd hole or the complement of an odd hole. This is known as the Strong perfect graph conjecture. The only if part is trivial; the if part is still open. Chvátal suggested considering the following class of Berge graphs (that is, graphs with no induced subgraph isomorphic to an odd hole or the complement of an odd hole): First, given any graph \(G\), define a graph \(\mathrm{Gal}(G)\) by letting the vertices of \(\mathrm{Gal}(G)\) be the edges of \(G\), and making two vertices of \(\mathrm{Gal}(G)\) adjacent if and only if the corresponding two edges of \(G\) share an endpoint and their other two endpoints are nonadjacent in \(G\) (so that the two edges form a chordless path with three vertices in \(G\)). We call a graph \(G\) Gallai-perfect if, and only if, \(\mathrm{Gal}(G)\) contains no odd hole. We prove that every Gallai-perfect graph is perfect. The class of Gallai-perfect graphs includes all bipartite graphs, all complements of bipartite graphs, and all line-graphs of bipartite graphs. A dart is the graph with vertices \(a, b, c, d, e\) and edges \(ab, ac, bc, bd, cd, be\). We prove that every Berge graph with no induced subgraph isomorphic to a dart is perfect. The class of dart-free Berge graphs includes all claw-free Berge graphs (which, in turn, include all line- graphs of bipartite graphs and all complements of bipartite graphs) as well as all diamond-free Berge graphs (which, in turn, include all line- graphs of bipartite graphs as well as bipartite graphs).
    0 references
    0 references
    strong perfect graph conjecture
    0 references
    Gallai-perfect graphs
    0 references
    dart
    0 references
    Berge graph
    0 references
    dart-free Berge graphs
    0 references
    claw-free Berge graphs
    0 references
    diamond-free Berge graphs
    0 references
    line-graphs of bipartite graphs
    0 references
    bipartite graphs
    0 references
    dart-free perfect graphs
    0 references
    clique number
    0 references
    0 references

    Identifiers