Coloring perfect graphs with no balanced skew-partitions

Abstract

We present an $O(n^5)$ algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present $O(n^7)$ time algorithm that colors them.

References in corpus (2)

• Combinatorial optimization with 2-joins
• Decomposing Berge graphs and detecting balanced skew partitions

Cited by in corpus (3)

• Clique-Stable Set separation in perfect graphs with no balanced skew-partitions
• Colouring perfect graphs with bounded clique number
• On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs