令 G 是一个阶为^ 的连通图,对 于 G 中的任意两个顶点^和 & 用D ( u , v)表 示 G 中一条最长的u- P路的长度。G 的一个Hamiltonian-染色是把颜色分配到顶点上的一种颜色分配方法f： V(G) — N * ,使得对于G 中的任意两个顶点w和 v都 有 D(u, v) + |f(u)- f(v)|> n - 1。G 的一个Hamiltonian-染 色 f的 值hc( f)等于分配给 G 的顶点的最大颜色值,即hc( f) = max{f(u) ： u e V (G)}。G 的 Hamiltonian-色数是 hc(G) = min{hc( f )：f是 G 的 Hamiltonian-染色}。若 hc( f) = h c ( G ) ,则称 Hamiltonian-染色 f是 G 的一个最优的Hamiltonian-染色。2OO2 年 ,Chartrand给出了连通图G 的一个Hamiltonian-色数的一个下界,hc(G) > ( n-1)2+1-D ( G ) 0本文借Hamiltonian-般的下界并刻画获得这个下界的树图。进而,我们确定满足一些特定Hamiltonian-Hamiltonian-染色。