Linear algorithm for finding list edge-colorings of series-parallel graphs

Tomoya Fujino, Shuji Isobe, Xiao Zhou, Takao Nishizeki

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| ≥ max{4, d(v), d(w)} for each edge e = vw or (ii) the maximum degree of G is at most three and |L(e)| ≥ 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

Original languageEnglish
Pages (from-to)186-190
Number of pages5
JournalIEICE Transactions on Information and Systems
Issue number2
Publication statusPublished - 2003 Feb


  • Algorithm
  • List edge-coloring
  • Series-parallel graph


Dive into the research topics of 'Linear algorithm for finding list edge-colorings of series-parallel graphs'. Together they form a unique fingerprint.

Cite this