IEICE TRANSACTIONS on Fundamentals
Generalized Vertex-Colorings of Partial k-Trees
Summary :
Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.671-678
- Publication Date
- 2000/04/25
- Publicized
- Online ISSN
- DOI
- 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
Xiao ZHOU, Yasuaki KANARI, Takao NISHIZEKI, "Generalized Vertex-Colorings of Partial k-Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 4, pp. 671-678, April 2000, doi: .
Abstract: Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_671/_p
Copy
@ARTICLE{e83-a_4_671,
author={Xiao ZHOU, Yasuaki KANARI, Takao NISHIZEKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Generalized Vertex-Colorings of Partial k-Trees},
year={2000},
volume={E83-A},
number={4},
pages={671-678},
abstract={Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Generalized Vertex-Colorings of Partial k-Trees
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 671
EP - 678
AU - Xiao ZHOU
AU - Yasuaki KANARI
AU - Takao NISHIZEKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - Let l be a positive integer, and let G be a graph with nonnegative integer weights on edges. Then a generalized vertex-coloring, called an l-coloring of G, is an assignment of colors to the vertices of G in such a way that any two vertices u and v get different colors if the distance between u and v in G is at most l. In this paper we give an algorithm to find an l-coloring of a given graph G with the minimum number of colors. The algorithm takes polynomial time if G is a partial k-tree and both l and k are bounded integers.
ER -
English
