有限制条件的平面图的均匀染色

来源 :山东大学 | 被引量 : 0次 | 上传用户:hfxwh6
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  设G是一个图,图G的一个顶点染色是指k种颜色1,2,…,k对G的各个顶点的一个分配,且G的任意两个相邻顶点都分配到不同的颜色,令Vi记颜色为i的顶点的集合,如果图G的一个顶点染色对所有的i,j满足‖Vi|-|Vj‖≤1,那么称这一染色为图G的一个均匀k-染色,图G具有均匀k-染色的最小整数k称为G的均匀色数,记为Xe(G)。  W.Meyer[1]证明了:任意树T都存在均匀(「Δ(T)/2(?)+1)-染色。并提出了以下猜想:  猜想1:对于任意一个既不是完全图也不是奇圈的连通图G,有Xe(G)≤Δ(G)。  Hajnal和Szemerédi[2]较早地证明了:任意图G,对于任意的整数k≥Δ(G)+1,都存在均匀k-染色。Yap和Zhang[10]证明了:最大度Δ≥13的任意平面图G,对任意整数m≥Δ,都存在均匀m-染色。  Lih和Wu[6](Yap[12])证明了:如果图G是一个连通的二部图,且不是完全二部图K2m+1,2m+1,m≥0,那么G存在均匀Δ-染色。基于这一结果,Chen,Lih和Wu提出了以下猜想:  猜想2:如果图G是一个既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,m≥0的连通图,那么G存在均匀Δ-染色。  Yap和Zhang在[7]中证明了最大度Δ≥3的连通的外平面图G存在均匀Δ-染色;在[9]中证明了:最大度Δ≥|G|/3+1的图G存在均匀Δ-染色。  本论文首先叙述了与均匀染色相关的一些背景知识,第二,三,四章分别详细地论述了以下结果:  1.任意一个阶为n的平面图G,如果围长g≥4,那么有e≤2n-4,且δ≤3;如果g≥ 6,那么有e≤3/2(n-2),且δ≤2。我们可以证明,如果Δ≥9和g≥4,或者Δ≥8和g≥6,那么平面图G存在均匀Δ-染色;
其他文献
  线性二次最优控制问题不但可以模拟现实世界中的很多现象,而且可以近似一些复杂的问题;同时其结构又相对简单,处理方便,因而成为现代控制理论中的一类重要问题。不管是确
  本论文给出了非参数回归模型中估计单调回归函数的一个惩罚局部多项式估计,除了单调性,新提出的估计在单调性和渐近性质之间达到了平衡。比起单调估计的惯用技术,新估计
  在铸造工艺中,铸件的充型过程非常重要,充型过程控制的优劣,将直接影响到液体的热传导和凝固。对此,本文对铸件充型过程进行了数值模拟。为简单起见,本文主要考虑的是一个二维
本文主要研究正交约束下的非均衡Procrustes问题:给定矩阵A∈Rn×n,B∈Rn×k,n>k,使得‖AQ-B‖F最小化,其中QTQ=Ik,Q∈Rn×k.全文共分为四章. 第一章是绪论部分,主要介绍了正交约
  在生命科学中,许多问题都可以抽象为计算机科学与数学中关于序列、树和串的组合问题。本文主要研究两个重要的生物信息学问题:寻找motif问题和RNA折叠问题。这两种问题简
  求解非线性矩阵方程的问题主要是通过分析所给方程参数的性质来得到方程的解。由于Hermite正定解在实际中应用较多,所以我们只讨论此类解的情况。在现实生活中,方程X-A*X
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
教学目标(1)诵读:熟读成诵,读出文章韵味。(2)积累:掌握文中重点字词句的含义。(3)感悟:感受作者的特殊心境,领悟作者的人生态度。教学重点指导学生熟读成诵,积累文言字词。
本文主要讨论了两个模型,是出现在半导体器件和等离子体里的一类一维双极量子流体力学模型,即双极量子Euler?poisson方程模型.模型一中,普朗克常量为ε=1,方程由质量守恒方程
耐久跑是一项运动强度较大的项目,对初中女生的心理、意志、品质、耐心都有较高的要求。耐久跑是提升学生心肺功能、增强学生身体体质、发展学生意志品质的重要途径,这一项目是