@inproceedings{034b343c9af84d51b134c0bd404c279c,

title = "A linear algorithm for edge-coloring partial k-trees",

abstract = "Many combinatorial problems can be efficiently solved for partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no linear-time algorithm has been obtained for partial k-trees. The best known algorithm solves the problem for partial k-trees G in time O(nΔ 22(k+1) where n is the number of vertices and Δ is the maximum degree of G. This paper gives a linear algorithm which optimally edge-colors a given partial k-tree for fixed k.",

author = "Xiao Zhou and Nakano, {Shln Ichi} and Takao Nishizeki",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1993.; 1st Annual European Symposium on Algorithms, ESA 1993 ; Conference date: 30-09-1993 Through 02-10-1993",

year = "1993",

doi = "10.1007/3-540-57273-2_76",

language = "English",

isbn = "9783540572732",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "409--418",

editor = "Thomas Lengauer",

booktitle = "Algorithms ESA 1993 – 1st Annual European Symposium, Proceedings",

}