Opposition graphs are strict quasi-parity graphs (Q1118614)

From MaRDI portal
Revision as of 11:12, 30 July 2024 by Openalex240730090724 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    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
    0 references
    opposition graph
    0 references
    chordless path
    0 references
    strict quasi-parity graph
    0 references
    0 references
    0 references
    0 references