【摘 要】
:
如果一个图G的选择数等于它的色数,即Ch(G)=X(G),则称图G是色一可选择的。关于图的色一可选择性,2002年Ohba给出猜想:任意一个顶点的个数小于等于2X(G)+1的图都是色一可选择的。
论文部分内容阅读
如果一个图G的选择数等于它的色数,即Ch(G)=X(G),则称图G是色一可选择的。关于图的色一可选择性,2002年Ohba给出猜想:任意一个顶点的个数小于等于2X(G)+1的图都是色一可选择的。目前,针对一般的图,对Ohba猜想的研究还没有突出的进展。2005年Reed和Sudakovr用概率方法证明了Ohba猜想的一个较弱的形式:若|V(G)|≤5x(G)/3-4/3,则Ch(G)=X(G)。同时,他们指出Ohba猜想是渐进地正确的。除此之外,人们只是对某些特殊的图类验证了Ohba猜想的正确性。由于每一个X-色图都是一个完全X-部图的子图,容易发现Ohba猜想成立当且仅当其对完全多部图成立。目前,对于至少有一部的顶点个数大于3的完全多部图,已有的结果只是证明了恰好有一部的顶点个数为4,或5,或6的完全多部图,即对图Kt+2,3,2*(k-t-2),1*t(其中t≤4且k≥t+2)及其所有k-色子图Ohba猜想成立。本文证明了 Ch(Kt+2,3,2*(k-t-2),1*t)=X(Kt+2,3,2*(k-t-2),1*t)=k,其中t为大于等于5的奇数,且k≥t+2。本文结果结合先前的结果表明Ohba猜想对图Kt+2,3,2*(k-t-2),1*t(t为奇数且t>3,k≥t+2)及其所有k-色子图Ohba猜想成立。
其他文献
带有自由面的渗流问题是近年来工程地下水重点研究的问题之一。在以往的研究过程中所使用的方法主要是有限元法,其一是移动网格法,其二是固定网格法。两种方法虽取得有效的结果
本文给出了求解非线性方程组的一个新的算法,首先将非线性方程组转化为一个非线性规划,再使用一个不使用罚函数和滤技术的算法求解这个非线性规划,在Jacobi矩阵一致列满秩的条件
随着社会的发展,社会各个方面对快速有效的身份验证的要求日益迫切。
由于生物特征是人的内在属性,具有很强的自身稳定性和个体差异性,因此是身份验证的理想依据。其中利用
关联分析是寻找人类疾病易感基因的主要工具,常用的数据采集方法有病例对照设计、匹配病例对照设计和家系设计。关联分析的一个关键问题是在各种设计下如何提高统计检验的功效
在函数逼近领域中,有关样条函数的研究占有极其重要的地位.利用样条函数,可以进行科研生产中经常涉及到的曲线/曲面的设计问题.我们知道,样条函数的每一段其实是多项式函数。那
关于Hom-系列代数近些年来有了许多研究,Hom-预李代数是预李代数通过代数变形而得到的一类Hom-型代数.Hom-预李代数与预李代数有着密切联系,同时Hom-预李代数也是一类特殊的Hom
本文讨论了如下p-Laplacian方程解的存在性问题{-div(|▽u(x)|p-2▽u(x))+K|u(x)|p-2u(x)=f(x,u(x)),x∈RN,u(x)∈W1,p(RN),其中p0为常数,f(x,u)满足条件limu→+∝f(x,u)up-l,这
本文讨论带有逐点控制约束条件的最优控制问题超收敛性。在有限元离散化中,控制变量用分片常函数近似,状态变量和伴随状态变量用分片线性函数近似,并重新构造控制变量u的插值uI.