New properties of perfectly orderable graphs and strongly perfect graphs (Q1185094): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3222875 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3347930 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4229265 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of recognizing perfectly orderable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A class of strongly perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on superbrittle graphs / rank | |||
Normal rank |
Revision as of 17:17, 15 May 2024
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