论文部分内容阅读
一个n阶连通图G的哈密顿染色c就是对这个连通图所有顶点的一个颜色分配方案(每一个颜色用一个正整数来表不)，对于G中任意两个互不相同的顶点u和u，满足｜c(u)-c(u)｜+D(u,u)≥n-1，其中D(u，u)表不G中最长的u-u路的长度。Hc(c)表不在G的一个哈密顿染色c中分配给顶点的最大颜色值(正整数)，图G的哈密顿色数hc(G)是指最小的hc(c)(其中c取遍G的所有哈密顿染色)。对于n阶路Pn，G.Chartrand,L.Nebesky和P.zhang给出了结论：对于任意正整数n，有hc(Pn)=ac(Pn)≤(n-1/2)+1成立。并进一步得出：
对于任意奇数n≥7，有hc(Pn)=ac(Pn)≤(n-1/2)-(n-1)/2+4，在本文中，我们提出一种路的哈密顿染色的伪贪婪算法，并得出结论：对所有偶正整数n≥10，hc(Pn)=ac(Pn)≤(n-1)/2-n/2-[10/n]+6。对于偶正整数n≥10，这个结论改进了路Pn的哈密顿色数上界，并且否定了Chartrand，Erwin和zhang等人给出的关于路的对极色数的猜想。