Bipolarizable graphs (Q912868)

From MaRDI portal
Revision as of 01:34, 7 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Bipolarizable graphs
scientific article

    Statements

    Bipolarizable graphs (English)
    0 references
    0 references
    1990
    0 references
    Perfectly orderable graphs are those for which an order of the nodes can be found such that for any subgraph \(G'\) of G the sequential node coloring algorithm (``always use the smaller possible colour'') gives an optimal coloring for \(G'\). Bipolarisable graphs admit a perfect order such that for any chain \(P_ 4(a,b,c,d)\) of 4 nodes we have \(a>b\) and \(c<d\). This class of perfectly orderable graphs is compared with other known classes of perfectly orderable graph.
    0 references
    Perfectly orderable graphs
    0 references
    sequential node coloring algorithm
    0 references
    Bipolarisable graphs
    0 references

    Identifiers