重图的T-染色

重图的T-染色是图的T-染色的一个较为实用的部分,这是因为在研究频率分配时,干扰可能会在不同的水平上发生。由于一个重图G能够被剖分成K个不同部分,用G(V,G0,G1,……,GK-1)来表示G。重图G(V,G0,G1,…,GK-1)的一个T-染色是指一个函数f,f满足同时是Gi的T(i)染色,即:对i=0,1,……,K-1,{x,y}∈E(Gi)|f(x)-f(y)|T(i)。G的f染色的色数是指值不同的f(x)的个数,记作:XT(f)。其中x∈V(G)。G的f染色的跨度等于m ax|f(x)-f(y)|,记作:spT(f),其中{x,y}∈E(G)。G的T-染色的色数和跨度分别记作XT(G)和spT(G),当f取遍所有G的T-染色时,XT(G)=m inXT(f),spT(G)=m inspT(f)。本文将给出一些关于重图的T-染色的已知结论,同时还将给出一种计算重图的spT的新算法。