关于图的均匀染色理论的继续研究

来源 :山东大学 | 被引量 : 0次 | 上传用户:bolen9999
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图均为有限、简单、无向图,对于任意一个图G,的顶点集合,阶(顶点数),边集合,边数,最大度,最小度,围长,直径和面集,分别用V(G),∣G∣,E(G),∣E∣,△(G),δ(G),g(G),d(G)和F(G)来表示.在不引起混淆的情况下,我们把△(G),δ(G),g(G),d(G)简记为△,δ,g和d.   图G的一个正常k-顶点染色是指k种颜色在V(G)上的一种分配,使得任意两个相邻的顶点分配以不同颜色.若图G有一个正常k-顶点染色,就称G是k-顶点可染色的.图G的点色数是指使G有正常k-顶点染色的数k的最小值,用x(G)表示.   设φ是图G的一个正常的顶点染色,若φ的任何两种不同颜色所染的顶点数目至多相差1,称φ是G的一个均匀染色.如果φ足图G的一个均匀k-顶点染色,称φ是G的一个均匀k-染色.图G可进行均匀k-染色的最小整数七称为G的均匀色数.记为xe(G).   现在已经有了很多关于图的均匀染色的结论,比较著名的是Hajnal和Szemerédi得到的这个结果:   Hajnal-Szemerédi定理:给定一个正整数r,如果一个图G最大度不超过r,那么这个图G存在一个均匀(r+1)-染色.   关于均匀染色理论,有以下两个猜想.   猜想1:设G是一个连通图.如果G既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,△(G)=△,那么G存在均匀△-染色.   猜想2:设r≥3,如果对于图G的任一条边xy,都有d(x)+d(y)≤2r,并且G不能均匀r-染色,那么G一定含有kr+1或者km,2r-m.(m为奇数)   本文所得到的第一个结论是证明了猜想2在一种特殊情况下是成立的.   定理2.1当r>3时,在图G中只有一对邻点va,vb满足d(va)+d(vb)=2r,其余各对邻点的度数之和都小于2r,那么图G可以均匀r-染色.   在本文中,我们还定义了一种新的染色-树染色.图G的(t,k,d)-树染色是指把图G的点集分解为V1,V2,…,Vt,即用t中颜色对图G的顶点进行染色,使得对每个Vi,(1≤j≤t),它的导出子图G[Vi]的任何一个分支都是直径至多为K,最大度至多为d的树,(k≥0,d≥0).图G存在(t,k,d)-树染色的最小的t称之为G的(k,d)-树色数,记为Xk,d(G).   图的均匀(t,k,d)-树染色是指G存在一个(t,k,d)-树染色,v1,v2,…,vt是各个颜色的顶点集合,并且对于任意的i和j(1≤i≤j≤t),都有||vi|-|vj||≤1.图G存在均匀(t,k,d)-树染色的最小的t我们称之为G的均匀(k,d)-树色数,记为Xk,d=(G).   图的全均匀(t,k,d)-树染色是指对所有的t≥t,G都存在一个均匀(t,k,d)-树染色,图的全均匀(k,d)-树色数记为Xk,d≡(G).若k=+∞,d=+∞,我们就把(t,k,d)-树染色称为t-树染色,把均匀(t,k,d)-树染色称为均匀t-树染色.最小的t-树染色称为点荫度,均匀t-树染色中最小的t称之为均匀点荫度,记为va=(G),全均匀点荫度记为va≡(G).   针对均匀树染色,主要得到了下面的两个结论:   定理3.1设G为-平面图且围长≥5.则全均匀点荫度va≡(G)≤3.   定理3.2设G为一平面图且围长≥6.若G为森林,则全均匀点荫度va≡(G)=1;否则全均匀点荫度va≡(G)=2.
其他文献
本文所讨论的图均为有限无向的简单连通图.   图的染色问题是图论研究的经典领域.张忠辅等人在全染色的基础上,提出了邻点可区别全染色和邻点强可区别全染色的概念.设G(V,
21世纪是科技信息迅速发展的时代,各行各业对现代技术都表现出了强烈的依赖性,同时也体现出了对其极高的要求。计算机辅助几何设计(CAGD)作为信息集成、数据集成、产品开发的重要
2002年,Fomin和Zelevinsky在文[FZ1,FZ2]中引入了cluster代数的概念,用来研究量子群的典范基和代数群的整体正性之间的联系.这种理论很快就和数学中的许多分支产生了密切的联
学位
设G=(V,E)是有限的无向简单图,其中V和E分别为G的点集与边集.图G的Smarandachely邻点可区别I-全染色是一个满足相邻顶点色集合互不包含的点边关系不正常的全染色.把染色方法中
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
我国学前儿童语言教育专家认为儿童学习语言有三大特性:易行性、积累性、和渗透性,其中渗透性指的是语言学习是随时随n地地进行的,儿童不必为学习语言而付出额外的智力负担。儿
小学数学不会自发产生与现实生活的联系。运用数学知识和方法解决一些简单的实际问题,需要采用切实可行的方法。本文围n绕小学数学生活化策略展开,旨在进一步拓宽小学数学教学
在这篇文章中我们报告了Donaldson-Thomas不变量的基本理论。这些不变量足发牛在Calabi-Yau三维流形上的现象。本文首先介绍了Donaldson-Thomas理论的基础知识,然后给出了一
学位
非线性矩阵方程是数值代数和非线性分析等领域研究的重要课题之一.其在控制理论,动态规划,统计,随机渗入,排队理论,梯形网格等多个领域都有很重要的应用.本文研究了非线性矩
ABC猜想由David Masser[7]and Joseph Osterlé[9]于1985年提出.   ABC猜想令a,b,c为非零整数,且两两互素,满足a+b+c=0.则对任意的∈>0,存在κ(∈)>0,使得   ABC-hit是指满足
学位