完全多部图是色-可选择图的必要条件

来源 :华南师范大学 | 被引量 : 0次 | 上传用户:jiu_yue9
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
如果图G满足xl(G)=x(G),则称图G是色-可选择图。色-可选择图的充分条件已经有了大量的研究。2012年,Noel,Reed和Wu证明了Ohba猜想:如果图G满足|V(G)|≤2x(G)+1,则图G是色-可选择图.通过大量的研究已经得到:图K(2*k)是色-可选择的;当k≥3时,图K(3*1,2*(k-1))和图K(3*2,2*(k-2))是色-可选择的;当k是奇数时,图K(4*1,2*(k-1))是色-可选择的。但是,当k是偶数时,图K(4*1,2*(k-1))不是色-可选择图。另外,完全k部图K(3*k),图K(4*k),图K(5*1,2*(k-1))等都不是色-可选择图。  寻找色-可选择图时只需考虑完全多部图,但这类图有很多,如果先研究完全多部图是色-可选择图的必要条件,则这样可以缩小色-可选择图的的搜索范围,对以后研究色-可选择图具有非常重要的意义。  本文我们得到了色-可选择图的5个必要条件,全文共分为三个部分。  第一部分:阐述了与本论文研究问题相关的色-可选择图的背景,阐述本文的主要结论。  第二部分:给出两种简单完全多部图(二部图和图K(1*(k-2),m*1,n*1))是色-可选择图的必要条件。  第三部分:给出一般完全多部图K(n1,n2,…,nk)是色-可选择图的必要条件和两种特殊完全多部图K(3*t,2*(k-t)),K(4*l,3*r,2*t)是色-可选择图的必要条件。
其他文献
在求解线性互补问题中,模基矩阵分裂迭代法是一个有效的求解方法.本文利用模方程的思想继续探究线性互补问题,建立了求解H+-矩阵线性互补问题的广义加速模基二步分裂及二级分裂
设G是一个简单图,G的顶点集合是V(G),边集合是E(G)以及块数是c。若G是连通图且对于任何一个顶点v∈V(G),G-v都有完美匹配,则称图G是因子临界图。  图的最大匹配计数和完美匹配
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
期刊
引言rn课堂是激情燃烧的动感地带,是学生求知、创造、展示自我、体验成功的平台.学生的潜力是无限的,给孩子多大的舞台,他就能跳出多美的舞蹈.“教学不仅仅是一种告诉,更多的
期刊
学位
学位
该文在对Lie双代数和Lie bialgebroids作统一的代数推广的基础上提出了广义Lie双代数的概念,给出了一种构造广义Lie双代数的方法,并得到一些具体的广义Lie双代数.对一般的线
该文用初等方法给出了方程x±6=Dy无非平凡整数解的充分条件.