IC-平面图的非正常染色

来源 :中国矿业大学 | 被引量 : 0次 | 上传用户:mkkkj2009
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论起源于Konigsberg七桥问题,由此引出了一系列的研究方向,其中的一个重要研究分支是图的染色理论,图的经典染色问题已经进行了多方面的推广,图的非正常染色就是其推广之一.此篇文章所研究的图均为简单、有限、无向的非空图.对于一个图G=(V,E),我们令E=E(G),V=V(G),F=F(G),δ(G)和△(G)分别表示图G的边集、顶点集、面集、最小度和最大度.若k是一个正整数,有映射φ:V→{1,2,...,k},若对于(?)uv∈E,总满足φ(u)≠φ(v),则称映射φ是图G的一个正常点染色,简称图G是正常k-可染的.如果我们将图G的顶点集合划分为子集V1,V2,...,Vk,当且仅当满足条件V1,V2,...,Vk是独立集时,得到图G是正常k-可染的.以正常染色为基础,我们放宽条件就得到了有关图的非正常染色的概念:设有k个非负整数d1,d2,...,dk,如果图G的顶点集合可以划分成V1,V2,...,Vk这k个子集合,对于上述的每一个Vi我们作出它的点导出子图并令其为G[Vi],其最大度至多为di,其中i=1,2,...,k,那么称图G是非正常(d1,d2,...,dk)-可染的,有时我们简写为(d1,d2,...,dk)-可染的.本文主要是将之前的研究结果进行改进并得出了有关IC-平面图的非正常染色的相关结论.第一章,我们介绍了图的染色理论相关的基本概念同时给出了文章中所用到的符号,接下来我们简述了图的非正常染色的定义并且概述了其研究现状,最后给出了本文的主要结论.第二章,借助构造极小反例的方式,同时运用权值转移的方法证明了围长至少为6的IC-平面图是(3,0,0)-可染的.第三章,通过分析所研究的图的结构性质,设置初始权值,运用权值转移的方法证明了围长至少为7的IC-平面图是(1,0,0,0)-可染的.第四章,对本文的主要结果进行总结并做出展望.
其他文献
前人的研究表明,维多利亚模态(Victoria mode,简称VM)作为北太平洋20°N以北海表温度异常(sea surface temperature anomalies,简称SSTAs)经验正交函数(empirical orthogonal function;简称EOF)分解的第二模态,会通过与之相关的副热带/热带太平洋表层海气耦合及次表层海温异常沿赤道的演变,引发厄尔尼诺/南方涛动(El N
随着地球能源危机的加剧,光催化分解水制氢技术被认为是解决全球能源问题的有效途径。光催化剂是光催化制氢反应的基础。传统的金属基半导体光催化剂存在成本高、制备工艺复
大鼠母性行为是一种具有高度动机性和良好组织性的社会行为。临床上使用的很多抗精神病药物,包括典型药物氟哌啶醇和非典型药物氯氮平、利培酮、奥氮平、喹硫平、阿立哌唑和
蔗糖磷酸化酶(Sucrose phosphorylase,SPase)催化蔗糖磷酸解反应生成α-D-葡萄糖-1-磷酸和D-果糖及其可逆反应。该酶具有葡萄糖基转移能力,可以将蔗糖分子的一个葡萄糖基转移至
P460钢属高强的高氮高钒设计正火钢,其强韧化的关键是基体中第二相粒子V(C,N)的析出,V(C,N)的析出一方面起到析出强化的作用,另一方面起到晶粒细化的作用。晶粒细化可以同时提高
目的:探讨慢性阻塞性肺疾病(COPD)稳定期患者营养状态与血清胰岛素样生长因子-1(IGF-1)、肿瘤坏死因子样凋亡微弱诱导剂(TWEAK)水平及生活质量之间的关系,为COPD营养不良的防治策略
污水排放标准的提高对常规污水处理工艺提出新的挑战,在原有污水处理技术单元上进行升级改造具有操作性强、工程量小等优点,因此被普遍采用。随着城市排水系统的完善及污水排
桫椤科(Cyatheaceae)植物是现存的唯一木本蕨类植物,极其珍贵,堪称国宝,被国家列为二级保护植物。但是国内开展相关研究较晚,且只局限于桫椤科植物的群落学、人工繁殖及引种栽
作为一种有效的抗生素,四环素具有广谱抗菌活性、低毒性、低成本等优点,已经被广泛地应用于治疗人和动物的细菌感染疾病。然而,四环素在生物体内新陈代谢较弱,不易被吸收,这
好氧颗粒污泥工艺(AGS)因其具有沉降性好、处理能力强、实现同时硝化反硝化、节省占地面积等优点被认为是最具发展前景的污水处理技术之一。目前利用AGS处理低浓度城市生活污