Abstract
In this paper we show that graph isomorphism and chromatic index are solvable in polynomial time when restricted to the class of graphs with treewidth ≤ k (k a constant) (or equivalently, the class of partial k-trees).
| Original language | English |
|---|---|
| Pages (from-to) | 631-643 |
| Number of pages | 13 |
| Journal | Journal of Algorithms |
| Volume | 11 |
| Issue number | 4 |
| Publication status | Published - 1 Dec 1990 |
| Externally published | Yes |