zbMATH — the first resource for mathematics

Coloring perfect \((K_ 4\)-e)-free graphs. (English) Zbl 0585.05007
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.)

05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
Full Text: DOI
[1] Berge, C, Farbung von graphen, deren samtliche bzw deren ungerade kreise starr sind, Wiss. z. martin-luther-univ., halle-Wittenberg math.-natur. reihe, 114-115, (1961)
[2] Berge, C; Chvatal, V, ()
[3] Golumbic, M, ()
[4] Grotschel, M; Lovasz, L; Schrijver, A, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, (1911) · Zbl 0492.90056
[5] Lovasz, L, A characterization of perfect graphs, J. combin. theory ser. B, 13, 95-98, (1972) · Zbl 0241.05107
[6] Parthasarathy, K; Ravindra, G, The validity of the strong perfect graph conjecture for (K_{4} − e)-free graphs, J. combin. theory ser. B, 26, 98-100, (1979) · Zbl 0416.05062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.