Generalized Vertex-Colorings of Partial K-Trees
Generalized Vertex-Colorings of Partial K-Trees
复制标题
部分 K 树的广义顶点着色
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
Takao Nishizeki
中科院分区：
文献类型：
--
作者：
Xiao Zhou;Yasuaki Kanari;Takao Nishizeki
设l是正整数，G是一个边权为非负整数的图. G的广义顶点染色，称为G的l-染色，是G的顶点的颜色分配，使得当G中任意两个顶点u和v之间的距离至多为l时，u和v得到不同的颜色。本文给出了一个求给定图G的最少色数l染色的算法。如果G是部分k-树，l和k都是有界整数，则该算法需要多项式时间。关键词：算法，广义顶点着色，l-着色，部分k-树
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 lcoloring 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. key words: algorithm, generalized vertex-coloring, l-coloring, partial k-tree