For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Generalized Vertex-Colorings of Partial k-Trees
Xiao ZHOU Yasuaki KANARI Takao NISHIZEKI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2000/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
algorithm, generalized vertex-coloring, l-coloring, partial k-tree,
Full Text: PDF(562.4KB)>>
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.