Coloring perfect \((K_ 4\)-e)-free graphs (Q1071025)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Coloring perfect \((K_ 4\)-e)-free graphs
scientific article

    Statements

    Coloring perfect \((K_ 4\)-e)-free graphs (English)
    0 references
    1987
    0 references
    This note proves the Strong Perfect Graph Conjecture for (K\({}_ 4-e)\)- free graphs from first principles. The proof directly yields an \(O(pn^ 2)\) algorithm for p-coloring perfect \((K_ 4-e)\)-free graphs. (Note: a previously published proof of this result by Parthasarathy and Ravindra is incorrect.)
    0 references
    0 references
    strong perfect graph conjecture
    0 references
    algorithm
    0 references
    coloring
    0 references
    (K4-e)-free graphs
    0 references
    0 references
    0 references