Opposition graphs are strict quasi-parity graphs (Q1118614)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Opposition graphs are strict quasi-parity graphs |
scientific article |
Statements
Opposition graphs are strict quasi-parity graphs (English)
0 references
1989
0 references
An opposition graph is a graph whose edges can be acyclically oriented in such a way that every chordless path on four vertices has its extreme edges both pointing in or pointing out. A strict quasi-parity graph is a graph G such that every induced subgraph H of G either is a clique or else contains a pair of vertices which are not endpoints of an odd (number of edges) chordless path of H. The perfection of opposition graphs and strict quasi-parity graphs was established respectively by Olariu and Meyniel. We show here that opposition graphs are strict quasi- parity graphs.
0 references
opposition graph
0 references
chordless path
0 references
strict quasi-parity graph
0 references