Coloring perfect graphs with no balanced skew-partitions
Author(s): Chudnovsky, Maria; Trotignon, Nicolas; Trunck, Théophile; Vuskovic, Kristina
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1761t| 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.