【摘 要】
：
图的染色理论是图论研究的热点问题之一.而均匀染色理论又是染色理论的进一步发展,在化学、生物学、计算机科学、工业生产和企业管理等领域中有着广泛的应用.图的团染色是图
论文部分内容阅读
图的染色理论是图论研究的热点问题之一.而均匀染色理论又是染色理论的进一步发展,在化学、生物学、计算机科学、工业生产和企业管理等领域中有着广泛的应用.图的团染色是图的点染色的一个变体,又称之为弱染色.本文主要研究的是图的团染色问题和图的均匀团染色问题.研究图的团染色问题和图的均匀团染色问题有着重要的应用背景和理论价值.第一章首先阐述了本文所需要的基本概念和定义.其次介绍了本课题的研究意义.最后对近十几年团染色的研究进展做了系统的梳理.第二章主要研究了平面图的团染色问题.Mohar和ˇkrekovski已证明了平面图是3-团可染色的(Electr.J.Combin.6(1999),#R26).在本章节中,我们运用归纳法进一步证明了任意平面图是3-团可染色的,并且设计了一个3-团染色平面图的线性时间算法(以上结果已经发表在《Operations Research Letters》杂志).第三章主要研究了无爪图的均匀团染色问题.Bacs′o和Tuza证明了以下定理:除了阶数大于3的无弦奇圈,最大度至多为4的无爪连通图是2-团可染色的,并且在(9)~2)时间内可以找到一个2-团染色(Discrete Math.and Theor.Comput.Sci.,2009,11(2),pp.15-24).本章运用归纳法证明了除了阶数大于3的无弦奇圈外,最大度至多为4的无爪连通图是均匀2-团可染色的,从而改进了Bacs′o和Tuza的上述结果.此外,我们改进了上述文献中所示的算法,给出了在该类图上一个均匀2-团染色的线性时间算法.
其他文献
近年来,电磁污染严重影响人类健康,吸波功能在军事领域日益受到重视,迫切需要发展高效廉价的新型微波吸收材料。在已报道的吸波材料合成方法中,氧化沉淀法由于具有产率高、设
近年来,因内部控制缺陷(Internal Control Weaknesses,以下简称ICW)导致的公司破产或财务舞弊现象在国内外频繁出现,世界各级政府颁布了一系列针对内部控制的法律制度,对企业
关于叶经济谱(leaf economics spectrum,LES)的研究已经进行了十多年,相关理论得到了很好的拓展和完善,但目前关于叶经济谱的研究尚存在着诸多争议。比如,在长期扰动因素影响
随着“十三五”规划和“创新、协调、绿色、开放、共享”五大发展理念的提出,煤炭行业可持续发展问题又一次成为社会关注的焦点。我国作为当今世界最大的煤炭生产国和消费国,
目的 本研究通过大鼠退变性颈椎椎间盘造模后应用二枝汤干预治疗该模型,进行细胞学与基因学实验。用手术方法获取大鼠颈椎椎间盘及髓核组织,采用PCR技术观察二枝汤对退变性颈
地震区划是世界上地震多发国家防御、减轻地震灾害的重要对策之一,是采取各项工程措施和编制社会经济发展、国土利用规划、防灾减灾规划的依据。目前地震区划图多采用工程地
[目的]检测硫化氢荧光探针CouMC与牙源性间充质干细胞的结合能力:比较不同牙源性间充质干细胞内源性硫化氢含量的区别;通过检测牙源性间充质干细胞成骨分化过程中内源性硫化
石墨烯在太赫兹到紫外的超宽频率范围内具有可调谐的电磁响应能力,因此在可调电磁波吸收器中有很好的应用前景。自石墨烯被发现以来,大量基于石墨烯的吸收结构被提出,工作频
复杂网络中节点重要性排序是当前学术界的研究热点之一,研究复杂网络中的关键节点对于改善复杂网络的可靠性有十分重要的意义和广泛的应用价值。近年来,许多研究人员对复杂网
载体是多相催化剂的重要组成部分,其性质对催化剂的性能有重要的影响。本论文主要考察了活性炭载体的孔结构、灰分及表面改性等因素对低固汞催化剂的催化性能的影响。主要包