该文考虑的图均为有限无向简单图.对于一个图G,我们用V(G)和E(G)分别表示它的顶点集和边集.对任意的x∈V(G),我们用deg(x)表示x在G中的次数,α(G)表示图G的最大独立集的顶点数目.图G的一个k-顶点染色是指对G的顶点分配k种颜色,1,2,…k;这个顶点染色是正常的是指任何两个相邻的顶点都分配不同的颜色.如果G有一个正常的k-顶点染色,就称G是k-顶点可染的.图G的顶点染色数x(G)是使得G能够k-顶点可染的最小的数k.图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色.图G的k-有界染色数x<,k>(G)是指对G进行k-有界染色所用的最少颜色数.该文中没有给出的定义可见[2].图的染色问题是图论中研究的主要问题之一.图的染色问题一般可分为顶点染色和边染色两类不同的染色,该文我们要考虑的是图的有界顶点染色问题.有界染包问题是对顶点染色问题的一个自然的限制,即对同一颜色的顶点数目的限制,在实际应用中,这可以是对可用的房间数,机器数或其它资源的数目限制.图的顶点染色问题的一个应用是作为时间表安排问题的一个模型(可参阅[17]),在这个模型中,顶点代表要安排的任务,两个顶点是相邻的表示它们代表的任务不重复,对此问题的一个自然的限制是在同一时间内不允许安排太多的任务,那么加上这个限制的时间表安排问题就可以用有界染色这个模型来表示.Hansen,Hertz和Kuplinsky研究了图的有界染色数的上界和下界,给出了一些定理.