New properties of perfectly orderable graphs and strongly perfect graphs (Q1185094): Difference between revisions

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.