New properties of perfectly orderable graphs and strongly perfect graphs (Q1185094): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Q759773 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Guy Chaty / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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 | |||
links / mardi / name | links / mardi / name | ||
Latest 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