Sufficient Condition and Algorithm for List Total Colorings of Series-Parallel Graphs
-
- MATSUO Yuki
- Graduate School of Information Sciences, Tohoku University
-
- ZHOU Xiao
- Graduate School of Information Sciences, Tohoku University
-
- NISHIZEKI Takao
- Graduate School of Information Sciences, Tohoku University
この論文をさがす
抄録
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.
収録刊行物
-
- IEICE transactions on fundamentals of electronics, communications and computer sciences
-
IEICE transactions on fundamentals of electronics, communications and computer sciences 90 (5), 907-916, 2007-05-01
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570572702555841152
-
- NII論文ID
- 110007519153
-
- NII書誌ID
- AA10826239
-
- ISSN
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles