IEICE TRANSACTIONS on Fundamentals
Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.5 pp.907-916
- Publication Date
- 2007/05/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e90-a.5.907
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuki MATSUO, Xiao ZHOU, Takao NISHIZEKI, "Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E90-A, no. 5, pp. 907-916, May 2007, doi: 10.1093/ietfec/e90-a.5.907.
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.5.907/_p
Copy
@ARTICLE{e90-a_5_907,
author={Yuki MATSUO, Xiao ZHOU, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs},
year={2007},
volume={E90-A},
number={5},
pages={907-916},
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.},
keywords={},
doi={10.1093/ietfec/e90-a.5.907},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 907
EP - 916
AU - Yuki MATSUO
AU - Xiao ZHOU
AU - Takao NISHIZEKI
PY - 2007
DO - 10.1093/ietfec/e90-a.5.907
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2007
AB - 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.
ER -
English
