Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs) (Q1175981)
From MaRDI portal
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
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