Edge-Coloring Partial k-Trees

Xiao Zhou, Shin Ichi Nakano, Takao Nishizek

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)


Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partial k-tree with the minimum number of colors for fixed k. & 1996 Academic Press, Inc.

Original languageEnglish
Pages (from-to)598-617
Number of pages20
JournalJournal of Algorithms
Issue number3
Publication statusPublished - 1996 Nov


Dive into the research topics of 'Edge-Coloring Partial k-Trees'. Together they form a unique fingerprint.

Cite this