Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs) (Q1175981)

From MaRDI portal
Revision as of 23:24, 29 January 2024 by Import240129110155 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)
scientific article

    Statements

    Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs) (English)
    0 references
    0 references
    0 references
    25 June 1992
    0 references
    A nonoriented graph is called quasi-perfectly orderable, if it admits an orientation which is kernel-perfect [\textit{P. Duchet}, Ann. Discrete Math. 9, 93-101 (1980; Zbl 0462.05033)] and has no subgraphs of the form \((b,a)\), \((b,c)\), \((c,d)\). It is proved that such a graph is strongly perfect [\textit{C. Berge} and \textit{P. Duchet}, Perfect graphs, Ann. Discrete Math. 21, 57-61 (1984; Zbl 0558.05037)]. This is a generalization of the result of \textit{V. Chvátal} [Perfect graphs, Ann. Discrete Math. 21, 63-65 (1984; Zbl 0559.05055)] concerning perfectly orderable graphs only.
    0 references
    kernel-perfect
    0 references
    strongly perfect
    0 references

    Identifiers