A Linear Algorithm for Edge-Face Coloring Series-Parallel Graphs

摘要

Let G be a series-parallel graph. In this paper, we present a linear algorithm of constructing an oriented binary decomposition tree of G. We use it to find 33 unavoidable subgraphs of G. Based on these 33 avoidable subgraphs, we can determine the edge-face chromatic number, denoted by χ_(ef)(G), of G where G is 2-connected and △(G) = 5. This completes the literature of determining χ_(ef)(G) for 2-connected series-parallel graphs.