Coloring perfect graphs with no balanced skew-partitions

Maria Chudnovsky, Nicolas Trotignon, Théophile Trunck, Kristina Vušković

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


We present an O(n5) algorithm that computes a maximum stable set of any perfect graph with no balanced skew-partition. We present O(n7) time algorithm that colors them.

Original languageEnglish (US)
Pages (from-to)26-65
Number of pages40
JournalJournal of Combinatorial Theory. Series B
StatePublished - Nov 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • 2-join
  • Berge graphs
  • Coloring
  • Homogeneous pair
  • Maximum stable set
  • Perfect graphs
  • Skew partition


Dive into the research topics of 'Coloring perfect graphs with no balanced skew-partitions'. Together they form a unique fingerprint.

Cite this