论文部分内容阅读
对任意图G,它的顶点集、边集、最大度、最小度分别用V(G)、E(G)、△(G)、δ(G)表示。图G=(V,E)中,设V’是V的一个非空子集。若图G有一个子图,其顶点集为V’,边集合为两端点均在V’中的边所构成的集合,那么这一了图称为V’在G中的导出子图,记为G[V’]。对于V的一个子集S,若S中任意两点在图G中不相邻,那么我们就称S为独立集;若S中任意两点在图G中相邻,那么我们就称S为团。图G的一个点边交替出现且点、边不重合的有限序列称为路。一条路所含的边数称为路的长度。图G=(V,E)中两点u,υ之间的所有路的路长最小值称为u,υ之间的距离。图G中任意两点之间距离的最大值称为图的直径。起点、终点重合,且内部点不重合的路称为圈。若图G的两个点u,υ之间有一条(u,υ)-路,那么称u,υ是联通的。因此,存在V的一个划分V1,V2,…,Vt,其中u,υ联通当且.仅当u,υ同属于Vi。导出子图G[V1],G[V2],…,G[Vt]称为G的分支。若G只有一个分支,则G是联通的。若图G是一个无圈的连通图,那么我们称其为树。若图G的各连通分支都是树,则称其为森林。若图G中任意不同的两点之间都有一条边存在,那么称图G为完全图。有n个点的完全图记为Kn。若图G=(V,E)中,点集V可以分成两个了集X和Y,使得图G中任意一条边有一个端点在X中,一个端点在Y中,则称图G为二部图。若X中每个点都与Y中每个点相邻,那么这样的二部图称为完全二部图。如果|X|=m,|Y|=n,那么这样的图可以记为Km,n。若图G=(V,E)中,点集V可以分成n个子集X1:X2,…,Xn,使得图G中任意一条边有一个端点在Xi中,一个端点在Xj中,则称图G为n部图。若Xi中每个点都与Xj中每个点相邻,那么这样的n部图称为完全n部图。如果|Xi|=li,那么这样的图可以记为Kl1,l2,…,ln。给定图G=(V,E),若V=S+K,且S为独立集,K为团,则称G为分裂图。本文主要研究图的均匀(t,k,d)-树染色。图G的均匀(t,k,d)-树染色是指把图G的点集分解为V1,V2,…,Vt,使得对于每个Vi,它的导出子图G[Vi]的任何一个分支都是直径至多为k、最大度至多为d的树(k≥0,d≥0),且对任意i,j(1≤i<j≤t),有||Vi|-|Vj||≤1。均匀(t,k,d)-树色数是指图G的所有均匀(t,k,d)-树染色中最小的t,记为χ=k,d。图的全均匀(t,k,d)-树色数是指对所有的t’≥t,G都存在一个均匀(t’,k,d)-树染色,且取值最小的t,记为χ≡k,d。本文首先将讨论一些特殊图的均匀树染色问题,即完全图、分裂图、完全二部图K1,n以及完全n部图Kl1,l2,…ln(li=1,1≤i≤k)。接着给出三个定义:(1)如果xmodn=y,我们称Mn(x)=y,其中n为整数。(2)Z(x)=max{3,max{k|Mi(x)=0,i≤k}}。(3)W(x)=max{j|(?)≥(?),i≤j}。当k=1时,对于完全二部图,我们证明:定理0.0.1(1)若M3(m)+M3(n)≥3,则χ≡1,1(Km,n)=(?)+(?);(2)若M3(m)+M3(n)≤2,且r=min{max{Z(m),Z(n)},W(m),W(n)},则χ≡1,1(Km,n)=(?)+(?)。对于完全n部图,我们也给出类似结果的证明。最后,当k没有限制时,对于完全二部图和完全n部图,我们在k=1的情况的基础上讨论均匀树染色的相关结果。