论文部分内容阅读
一般说来,图的着色问题最早起源于著名的"四色问题",染色问题不但有着重要的理论价值,而且,它和很多实际问题有着密切联系,例如通讯系统的频道分配问题,更有着广泛的应用背景.距离图是一类重要的无限简单图,设Z是全体整数集,D是一个正整数集,距离图G(Z,D)是这样的一类图:点集是Z,x,y相邻,若|x-y|∈D.它的染色问题和很多实际问题有着密切的关系.所谓图G的正常点着色是指这样一个映射f:V(G)→G<,k>={c<,1>,c<,2>,c<,3>,……c<,k>},使: u,v∈V(G),u,v相邻时,有:f(u)≠f(v).图G的点色数是χ(G)=min{k:V(G)→{c<,1>,c<,2>,c<,3>,……c<,k>}是图G的正常着色},而图的圆色数是其点色数的自然推广,Vince以星色数引入这个概念.设p,q均为正整数,且p≥2q,图G=(V,E)的(p,q)-着色是指这样一个映射c:V→{0,1,2,……p-1},使 xy∈E,‖c(x)-c(y)‖<,p>≥q,其中‖a‖<,p>=min{q,p-a}.圆色数χ<,c>(G)=inf{p/q:存在图G的一种(p,q)-着色}.而图G的分式着色c是从图的独立集族S到区间[0,1]的一个映射,使对任意点x,有:Σ<,x∈s,s∈S>c(s)≥1,而分式色数χ<,f>(G)≤χ<,c>(G)≤χ(G).当|D|≤3时,距离图G(Z,D)的点色数、圆色数、分式色数几乎都得到了圆满 的解决.但是,当|D|≥4这方面的结果还不多.另外,对于其他类型的集合D,也有一些结果.该文给出了一类点色数是3的距离图的具体着色,确定了某些|D|=4或5时距离图的点色数,利用点色数和圆色数的紧密关系,得到了另一类距离图的各种染色数,并讨论了图的star extermal性质.