刘维婵，张 欣

西安电子科技大学 数学与统计学院，西安 710071

1 引言

图论是一门古老的数学分支，它起源于1736年欧拉对于哥尼斯堡七桥问题的研究。近年来，图论学科的发展非常迅速且应用广泛，已渗透到诸如语言学、物理学、化学、电讯工程、计算机科学以及数学的其他分支中，特别在计算机科学中，图论在如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。

本文仅考虑简单的有限无向图。设G是一个图，用∆(G),δ(G),V(G)与E(G)分别表示图G的最大度，最小度，点集合与边集合，用|G|与‖G ‖分别表示图G的顶点数与边数。

本文主要研究图的均匀树染色问题。所谓图的均匀树k-染色是一个从图的点集合到数集{1,2,…,k}的映射 c，其满足对于任何 1≤i≤j≤k，都有 |c-1(i)-c-1(j)|≤1，并且由点集c-1(i)导出的子图为一个森林。使得图G具有均匀树k-染色的最小整数k称为图G的均匀点荫度，记为va=(G)。例如，完全二部图K9,9具有一个均匀树2-染色（每一个部染一种颜色即可），而不具有均匀树1-染色，从而va=( )K9,9=2。然而，容易验证完全二部图K9,9不具有均匀树3-染色（如图1的第一张图所示），从而在研究图的均匀树染色的过程中，还需要定义一个染色参数，即图的均匀点荫度阀值。所谓图G的均匀点荫度阀值va*=(G)是一个尽可能小的整数k，其使得对于任何一个不小于k的整数t，图G都具有均匀树t-染色。例如，完全二部图K9,9不具有均匀树3-染色，但是对于每个不小于4的整数k都具有均匀树k-染色（如图1的第二张图所示），从而va*=( )K9,9=4。显而易见，对于任何图G，都有va=(G)≤va*=(G)，并且va*=(G)与va=(G) 的差值可以很大。……