New properties of perfectly orderable graphs and strongly perfect graphs (Q1185094)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New properties of perfectly orderable graphs and strongly perfect graphs |
scientific article |
Statements
New properties of perfectly orderable graphs and strongly perfect graphs (English)
0 references
28 June 1992
0 references
We establish a property of minimal nonperfectly orderable graphs, and use this property to generate a class of perfectly orderable graphs which strictly contains all brittle graphs. This class is characterized by the existence, in each induced subgraph, of a vertex which is either the endpoint of no \(P_ 4\), or the midpoint of no \(P_ 4\), or the mid-point of exactly one \(P_ 4\) and the endpoint of exactly one \(P_ 4\). As a consequence, we show that the number of \(P_ 4\)'s in a minimal nonperfectly orderable graph is at least \({3\over 4}n\), where \(n\) is the number of vertices of the graph. Similar results are obtained for strongly perfect graphs.
0 references
perfectly orderable graphs
0 references
strongly perfect graphs
0 references