论文部分内容阅读
设G是阶数为n的连通图。对图G中任意不同的两顶点u和v，设D（u,v)为图G中最长的u-v路。阶数为n的连通图G的哈官、密顿染色就是对G中顶点染色（正整数）的一个分配，对G中任意不同的两顶点u和v，满足D（u,v）+|c(u)-c(v)|≥n-1。对于G的哈密顿色数hc(G)是最小的hc(c)取遍G的所有顶点的哈密顿染色。
近年来，图的哈密顿染色作为图论研究的热点问题被广泛的研究着，某皯特殊图的哈密顿色数已经得到了证明，在这篇文章里，我们主要讨论了毛毛虫的哈密顿染色，并确定了其哈密顿色数。