没有4-圈的可平面图是(4,4)-可着色的

来源 :华中师范大学 | 被引量 : 0次 | 上传用户:alexzhujun
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个图是k-可着色的,如果它的点集可以被划分为k个独立集。这是正常着色。本文主要研究非正常着色。设d1,d2,...,d2为k个非负整数。如果可以将G的顶点集V划分为fκ个子集V1,V2,...,Vk,使得对于任意的i=1,2,...,k,Vi的点导出子图G[Vi]的最大度数至多为di,则称图G是(d1,d2,...,d4)-可着色的。图中最短圈的长称为图的围长。著名的四色定理证明了每个可平面图是4-可着色的。由于存在不可.3各着色的平面图,那么寻找.3-可着色的充分条件引起了大多数研究学者的注意。关于3-着色最著名的结果是:没有3-圈的可平面图是3-可着色的。目前其他研究成果还有:没有(4,5,6,9)-圈的可平面图是3-可着色的,·没有(4,5,7)-圈的可平面图是3-可着色的;没有(4,5,8,9)-圈的可平面图是3-可着色的;没有(4,6,7,9)-圈的可平面图是3-可着色的;没有(4,6,8)-圈的可平面图是3-可着色的;没有(4,7,8,9)-圈的可平面图是3-可着色的。所有可平面图是(2,2,2)-可着色的。对于任意的(d1,d2),由于存在围长大于等于4的不可(d1,d2)-着色的平面图,因此我们考虑非正常二着色的问题都是在没有4-圈的基础上。目前已有的结论有:围长大于等于5的可平面图是(1,10),(2,6),(3,5),(4,4)-可着色的。对于任意非负整数d,围长大于等于6的可平面图是不可(0,d)-着色的。围长大于等于7的可平面图是(0,4)-可着色的。最近,Choi,Liu和Oum证明了没有4-圈的可平面图是(5,5)-可着色的。在本文中,我们进一步对没有4-圈的图的结构进行深入研究,证明了没有4-圈的可平面图是(4,4)-可着色的。
其他文献
X射线CT(computed tomography,简称CT)成像技术具有数据采集速度快和重建图像分辨率高等优点,被广泛应用于医学、工业检测等领域.但是,X射线辐射有诱发癌症等疾病的风险.因此,降低CT成像的X射线剂量是医生和患者共同关心的问题.降低X射线强度和减少X射线数量是两种常用的降低X射线剂量的方法,从而导致低信噪比投影数据和不完全投影数据的CT重建问题.因此研究低信噪比投影数据和不完全投
承包地调整是指在农村承包地承包期内,因自然灾害严重毁损承包地等特殊情形,通过法定程序对承包方(农户)的承包地进行适当调整的制度。农村承包地调整既不同于农村承包地收回,也不同于承包地交回,但是三种制度共同对农村承包地具有调节和分配作用。如今,农村承包地调整面临着规范冲突和现实困境。规范冲突体现在:法律价值相冲突、承包期间内进行农村承包地调整与农村土地承包经营权的物权效力存在矛盾、制定的村规民约与国家
大数据智能挖掘分析是当前大数据挖掘研究和应用发展的重要方向,问题任务的复杂性是其中的关键挑战,探索复杂任务的分解求解具有重要意义。目前,复杂任务求解方法(如专家式分
自乡村振兴确立为国家战略以来,关乎“三农”的一系列改革不断推进,农村宅基地资源的高效利用对于乡村振兴战略的实施具有重大现实意义。2018年中央“一号文件”提出宅基地“三权分置”制度改革,用于盘活闲置宅基地资源,激发宅基地的财产属性,推动农村集体产权制度改革。宅基地“三权分置”制度改革的是对传统“两权分立”格局的体系化变革,本质上是权利的重新配置与重塑。“农户资格权”作为政策性的表述,需要进行权利定
硒(Se)是人和动物生长发育必需的微量元素,对维持机体健康如降低死亡率、抗氧化、抗癌等有着重要作用。缺硒会引起家禽患白肌病,人类患克山病、大骨节病。在半发酵牛粪中添加
黄酮广泛存在于植物中并具有多种生物活性,其中槲皮素、山奈酚和黄芩素等作为Nrf2激动剂,研究热度高,表现出多种疾病的干预潜力。氧化应激和炎症反应参与多种疾病的发生与发
基于多裂缝开裂和应变硬化的两大独特优势,工程水泥基复合材料(ECC)受到各方面研究者的关注。相比于混凝土材料,粗骨料的去除以及纤维的加入使得ECC具有优越的延性,该材料也
二硫化钼(MoS2)是一种层状的过渡金属硫族化合物,随着层数减少至单层,Mo S2由间接带隙转化为直接带隙。相比于现在热点研究的零带隙的石墨烯材料而言,二维二硫化钼带隙可调,因此被广泛应用,比如光电探测、太阳能电池、传感器、场效应晶体管、催化、光电器件、能量存储等方方面面。但是二维MoS2是n型输运的半导体材料,单层MoS2发光效率较低,严重限制其在光电器件中的应用。因此实现其双极性,并提高发光效
随着中国5G商用的正式铺开,为云计算、大数据的发展打开了快车道,存储云、医疗云、金融云、交通云、教育云、社保云等各行业云平台正在快速推进。为了减少资源平台的重复性建设和相应费用,同时也为了方便更多的人可以通过较少的资源平台充分使用已有的数据资源,提高信息资源利用率,进而提高整个社会效益,数据共享必然成为未来的大趋势。大量新型应用和需求的快速涌现必将使得基于跨行业、跨领域的应用成为主流。在跨行业、跨
克拉玛依油田九8区由于受原油粘度过高、开发方式落后等因素的影响,多数油井生产时间短或近于停产。因此要求地质工作者在前人地质认识的基础上进行更进一步的探索,取得更加