Bipartable graphs (Q1080439)

From MaRDI portal
Revision as of 15:15, 12 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
Bipartable graphs
scientific article

    Statements

    Bipartable graphs (English)
    0 references
    0 references
    1988
    0 references
    We consider a construction which associates with a graph G another graph G' such that if G' is a bipartite graph, G is perfectly orderable. For such a graph G we give a polynomial algorithm for an optimal coloring by delivering a perfect order on his nodes. This class of graphs is shown to be different from the known classes of perfectly orderable graphs.
    0 references
    bipartite graph
    0 references
    polynomial algorithm
    0 references
    optimal coloring
    0 references
    perfectly orderable graphs
    0 references

    Identifiers