Name
Abstract | ||
|---|---|---|
A graph is perfect if the chromatic number of every induced subgraph equals the size of its largest clique, and an algorithm of Grötschel, Lovász, and Schrijver [9] from 1988 finds an optimal colouring of a perfect graph in polynomial time. But this algorithm uses the ellipsoid method, and it is a well-known open question to construct a “combinatorial” polynomial-time algorithm that yields an optimal colouring of a perfect graph. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jctb.2016.09.006 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Colouring algorithm,Perfect graph,Balanced skew partition | Journal | 122 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
5 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Aurélie Lagoutte | 2 | 24 | 4.98 |
| Paul D. Seymour | 3 | 2786 | 314.49 |
| Sophie Theresa Spirkl | 4 | 8 | 7.36 |