关于距离图着色问题的一点研究

来源 :东南大学 | 被引量 : 0次 | 上传用户:goonesownway
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一般说来,图的着色问题最早起源于著名的"四色问题",染色问题不但有着重要的理论价值,而且,它和很多实际问题有着密切联系,例如通讯系统的频道分配问题,更有着广泛的应用背景.距离图是一类重要的无限简单图,设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性质.
其他文献
该文分成两个部分:第一部分:保险公司如何根据多个不同的目标来选择个人代理人的薪酬方案?最常见的做法是由管理层参照他人的做法与已有的经验来进行方案选择.该文在分别对保
由于矩阵广义逆在许多领域中有着广泛的应用,如在微分和积分方程、算子理论、统计学、控制论、Markov链、最优化等.因此,自上个世纪中期以来矩阵广义逆就成为一个非常重要的
二十世纪三十年代P.Jordan最早给出了约当代数的概念.约当代数是一类十分重要的非结合代数,在很多领域都有广泛的应用.本文主要研究三维约当代数上的Rota-Baxter算子和Hom-预
一切生命活动的基础是细胞,细胞的活动构成一套精密而复杂的化学反应网络。因此研究这些相互作用的化学反应网络已成为系统生物学研究中的一个重要课题。为了研究复杂化学反
本文研究可数离散群以自同胚的方式作用在紧致度量空间上可能产生的各种混沌行为。  给定可数离散群G,对于G作用的拓扑动力系统,我们引入了局部弱混合和Li-Yorke混沌的概念,证
所谓群G是Core-有限的,是指群G的每个子群H均满足H/H是有限的.在文[3]中,对偶地定义了S(A,C)-群.一个群G,若对G中任意子群(阿贝尔子群,循环子群)H有|H:H|
该文的工作,主要有两点:第一,对路染色猜想和Cerny猜想做了一个综述,其中包括了数十年来的经典结论,和最近的一些新的进展.在路染色问题和Cerny猜想这两个问题上,世界各地的
该文主要研究孤立子与可积系统理论中精确求解非线性发展方程,构建有限维可积Hamiton系统和Painlevé性质的应用等几方面.第二章中研究了非线性发展方程的精确解.第三章研究
在本文中,我们将讨论具有Kirchhoff型的非线性波方程初值问题解在一定条件下的渐近性质,通过研究最后发现,文中所考虑的方程的初值解与热方程的初值解具有一定的相似性.本文所考
他是一位从普通的工人家庭走出来的优秀医生,他以丰富的临床经验和视病人如亲人的高尚医德挽救了无数患者的生命。他更是一名出色的医院管理工作者,自1999年走上院长领导岗