Title | ||
---|---|---|
Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs |
Abstract | ||
---|---|---|
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such 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 for given L. In this paper, we give a sufficient condition for a series-parallel graph to have a list total coloring, and we present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G and L satisfy the sufficient condition. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1093/ietfec/e90-a.5.907 | IEICE Transactions |
Keywords | Field | DocType |
sufficient condition,series-parallel graphs,total coloring,list total coloring problem,list total colorings,linear-time algorithm,graph g,series-parallel graph,incident element,list total coloring,list total,algorithm | Discrete mathematics,Edge coloring,Complete coloring,Combinatorics,Total coloring,Fractional coloring,List coloring,Algorithm,Brooks' theorem,Greedy coloring,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
E90-A | 5 | 0916-8508 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yuki Matsuo | 1 | 13 | 1.65 |
Xiao Zhou | 2 | 325 | 43.69 |
Takao Nishizeki | 3 | 1771 | 267.08 |