TY - JOUR

T1 - List total colorings of series-parallel graphs

AU - Zhou, Xiao

AU - Matsuo, Yuki

AU - Nishizeki, Takao

PY - 2005/3

Y1 - 2005/3

N2 - A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|≥min{5,Δ+1} for each vertex v and |L(e)|≥max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ≥4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.

AB - A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|≥min{5,Δ+1} for each vertex v and |L(e)|≥max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ≥4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.

KW - Linear algorithm

KW - List edge-coloring

KW - List total coloring

KW - NP-complete

KW - Series-parallel graph

UR - http://www.scopus.com/inward/record.url?scp=13544275648&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=13544275648&partnerID=8YFLogxK

U2 - 10.1016/j.jda.2003.12.006

DO - 10.1016/j.jda.2003.12.006

M3 - Article

AN - SCOPUS:13544275648

SN - 1570-8667

VL - 3

SP - 47

EP - 60

JO - Journal of Discrete Algorithms

JF - Journal of Discrete Algorithms

IS - 1

ER -