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

DOI10.1016/0012-365X(91)90100-GMaRDI QIDQ1175981zbMATH OpenFDO

Authors Pierre Duchet, Stephan Olariu

Publication date 25 June 1992

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90100-G

zbMATH Keywords

kernel-perfectstrongly perfect

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• New classes of perfectly orderable graphs
• Quasi-brittle graphs, a new class of perfectly orderable graphs
• Perfectly orderable graphs are quasi-parity graphs: a short proof
• All variations on perfectly orderable graphs
• Generalized neighbourhoods and a class of perfectly orderable graphs

Cites work

• Graphes Noyau-Parfaits
• scientific article; zbMATH DE number 3889565 (Why is no real title available?)
• scientific article; zbMATH DE number 3891425 (Why is no real title available?)
• scientific article; zbMATH DE number 4095496 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Topics on perfect graphs

Cited in

(8)

• Generalized neighbourhoods and a class of perfectly orderable graphs
• Paw-free graphs
• All variations on perfectly orderable graphs
• Perfectly orderable graphs and almost all perfect graphs are kernel \(M\)- solvable
• Perfect graphs, kernels, and cores of cooperative games
• scientific article; zbMATH DE number 15158 (Why is no real title available?)
• 1-perfectly orientable \(K_{4}\)-minor-free and outerplanar graphs
• New classes of perfectly orderable graphs

This page was built for publication: Graphes parfaitement ordonnables généralisés. (Generalized perfectly orderable graphs)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1175981)