Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. (English) Zbl 0651.68079

Algorithm theory, Proc. 1st Scand. Workshop, Halmstad/Sweden 1988, Lect. Notes Comput. Sci. 318, 223-232 (1988).
Summary: [For the entire collection see Zbl 0639.00043.]
We show that the graph isomorphism and chromatic index problems are solvable in polynomial time when restricted to the class of graphs with treewidth \(\leq k\) (k a constant) (or equivalently, the class of partial k-trees). Also, we show that there exist algorithms that find tree- decompositions with treewidth \(\leq k\) of graphs with treewidth \(\leq k\), in O(n 3) time, (k constant).


68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity


Zbl 0639.00043