Skip to main content

Coloring perfect graphs with no balanced skew-partitions

Author(s): Chudnovsky, Maria; Trotignon, Nicolas; Trunck, Théophile; Vuskovic, Kristina

To refer to this page use:
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.
Publication Date: Nov-2015
Electronic Publication Date: 29-Apr-2015
Citation: M. Chudnovsky, N. Trotignon, T. Trunck, K. Vu š kov i ć , Coloring perfect graphs with no balanced skew-partitions, J. Combin. Theory Ser. B 115 (2015) 26–65.
DOI: 10.1016/j.jctb.2015.04.007
Pages: 26 - 65
Type of Material: Journal Article
Journal/Proceeding Title: Journal of combinatorial theory. Series B.
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.