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

From MaRDI portal
Revision as of 14:11, 14 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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