ملخص: In this paper, we consider a class of degenerate Berge graphs. We give a coloring theorem for them and show how the algorithmic proof of this result suggests a polynomial combinatorial algorithm for [omega]-coloring any degenerate Berge graph, for fixed [omega]. This proof also allows us to get a combinatorial algorithm for optimally coloring in polynomial time any degenerate perfect graph which is a split-neighborhood graph.

لغة: إنجليزية