Loading...
Please wait, while we are loading the content...
Similar Documents
Finding balanced skew partitions in perfect graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Chudnovsky, Maria Lagoutte, Aurélie Seymour, Paul Spirkl, Sophie Theresa |
| Copyright Year | 2015 |
| Abstract | A graph G is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one; and it is known that this is equivalent to being perfect, that is, that the chromatic number of every induced subgraph equals the size of its largest clique. A skew partition in G is a partition (A,B) of V (G) such that G[A] is not connected and G[B] is not connected; and it is balanced if an additional parity condition of paths and antipaths is satisfied. In this paper we give a polynomial-time algorithm which, with input a Berge graph, outputs a balanced skew partition if there is one. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://web.math.princeton.edu/~pds/papers/skew/paper.pdf |
| Alternate Webpage(s) | https://web.math.princeton.edu/~mchudnov/detectbsp.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
