| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 5777677 | Journal of Combinatorial Theory, Series B | 2017 | 19 Pages |
Abstract
In this paper we first give a polynomial-time algorithm that, with input a perfect graph, outputs a balanced skew partition if there is one. Then we use this to obtain a combinatorial algorithm that finds an optimal colouring of a perfect graph with clique number k, in time that is polynomial for fixed k.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Maria Chudnovsky, Aurélie Lagoutte, Paul Seymour, Sophie Spirkl,