Multicolorings of series-parallel graphs

Xiao Zhou, Takao Nishizeki

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Let G be a graph, and let each vertex v of G have a positive integer weight ω(v). A multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.

Original languageEnglish
Pages (from-to)271-297
Number of pages27
Issue number2
Publication statusPublished - 2003 Nov


  • Coloring
  • Dynamic programming algorithm
  • Multicoloring
  • Series-parallel graph


Dive into the research topics of 'Multicolorings of series-parallel graphs'. Together they form a unique fingerprint.

Cite this