Coloring perfect graphs with no balanced skew-partitions

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

doi:10.1016/j.jctb.2015.04.007

Coloring perfect graphs with no balanced skew-partitions

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

Mathematics

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

Abstract

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

Original language	English (US)
Pages (from-to)	26-65
Number of pages	40
Journal	Journal of Combinatorial Theory. Series B
Volume	115
DOIs	https://doi.org/10.1016/j.jctb.2015.04.007
State	Published - Nov 1 2015

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

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

Access to Document

10.1016/j.jctb.2015.04.007

Cite this

@article{a519d043b07b486391232a14bbe4b7f1,

title = "Coloring perfect graphs with no balanced skew-partitions",

abstract = "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.",

keywords = "2-join, Berge graphs, Coloring, Homogeneous pair, Maximum stable set, Perfect graphs, Skew partition",

author = "Maria Chudnovsky and Nicolas Trotignon and Th{\'e}ophile Trunck and Kristina Vu{\v s}kovi{\'c}",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier Inc.",

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.jctb.2015.04.007",

language = "English (US)",

volume = "115",

pages = "26--65",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Coloring perfect graphs with no balanced skew-partitions

AU - Chudnovsky, Maria

AU - Trotignon, Nicolas

AU - Trunck, Théophile

AU - Vušković, Kristina

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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.

AB - 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.

KW - 2-join

KW - Berge graphs

KW - Coloring

KW - Homogeneous pair

KW - Maximum stable set

KW - Perfect graphs

KW - Skew partition

UR - https://www.scopus.com/pages/publications/84939252332

UR - https://www.scopus.com/inward/citedby.url?scp=84939252332&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2015.04.007

DO - 10.1016/j.jctb.2015.04.007

M3 - Article

AN - SCOPUS:84939252332

SN - 0095-8956

VL - 115

SP - 26

EP - 65

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Coloring perfect graphs with no balanced skew-partitions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this