New properties of perfectly orderable graphs and strongly perfect graphs

AbstractWe 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 P4, or the midpoint of no P4, or the mid-point of exactly one P4 and the endpoint of exactly one P4. As a consequence, we show that the number of P4's in a minimal nonperfectly orderable graph is at least 34n, where n is the number of vertices of the graph. Similar results are obtained for strongly perfect graphs