平面图的全染色、列表染色和无圈全染色

【摘要】本文所考虑的图都是有限简单图.我们用V(G),E(G),F(G),△(G),δ(G)和g分别表示平面图G的顶点集,边集,面集,最大度,最小度及围长.对任何一点υ∈V,我们把与υ相邻的所有点的集合记作N(υ),用d(v)=|N(v)|代表υ的度数.一个k-圈是长度为k的圈,其中3-圈也称作三角形.长度不超过5的圈称为短圈.图G的正常k-全染色是指用k种颜色对V(G)∪E(G)中的元素进行染色,使得相邻的或者相关联的两个元素染不同的颜色.使得图G存在正常的k-全染色的最小正整数k称为G的全色数,记作χ″(G).如果我们只对图G的顶点或者边进行染色,那么就可以分别得到图G的点色数χG)和边色数χ′(G).显然,X”(G)≥△+1.Behzad和Vizing各自独立提出下面这个著名猜想：对任意图G,△(G)+1≤x”(G)≤△+2.对于一般图来讲,该猜想在最大度为△≤5的图中已被证明是成立的.对于平面图而言,仅剩下△=6的情形是需要验证成立的.我们利用“充放电”的方法,求得了几类有限制条件的平面图的全色数.首先讨论了不含相交短圈的情形,得到如下结论：定理1假设G是最大度为△(G)≥7的平面图.如果3-圈与3-圈不相交,那么它的全色数χ″(G)=△+1.定理2假设G是最大度为△(G)≥7的平面图.如果3-圈与4-圈不相交,那么它的全色数χ″(G)=△+1.定理3假设G是最大度为△(G)≥7的平面图.如果5-圈与5-圈不相交,那么它的全色数X”(G)=△+1.然后讨论了不含带弦6-圈的平面图的染色问题,得到如下结论：定理4假设G是最大度为△(G)≥7的平面图.如果G不含带弦6-圈,那么它的全色数χ″(G)=△+1.继而讨论了最大度不大于5的平面图的全染色问题,得到如下结论：定理5假设G是最大度为△,围长为9的平面图,且存在一个整数t(>g)使得G不含有长度从g+1到t的圈.如果(a)(△,g,t)=(5,4,6)或者(b)(△,9,t)=(4,4,17),那么它的全色数χ″(G)=△+1.定理6假设G是最大度为3,围长为g9,每个顶点至多关联一个g-圈的平面图,且存在一个整数t(>g)使得G不含有长度从9+1到t的圈.如果G满足以下条件之一,那么它的全色数χ″(G)=△+1.(a)g=5且t≥29,(b)g=6且t≥17,(c)g=7且t≥13；(d)夕=8且t≥11,(e)g=9且t≥10.最后,从度和的角度研究了平面图的全染色问题.令s△=min{d(u)+d(v)+d(w)|uvw是G中的任意三角形}及δ△=min{d(u),d(v),d(w)|uvw是G中的任意三角形}.定理7假设G是最大度为△≥7的平面图.如果s△≥18且δΔ≥6,那么它的全色数χ″(G)=△+1.定理8假设G是最大度为△≥8的平面图.如果s△≥19且δΔ≥5,那么它的全色数χ″(G)=△+1.本文讨论的另一个问题是列表染色.对于图G的每一条边e,我们都给定一个颜色集合L(e),那么这个映射L就称为图G的一个边安排.如果图G存在边染色φ使得对任意边e∈E(G),都有φ(e)∈L(e),则称图G是L-边可染的.对于图G的任意一个满足条件|L(e)|≥κ的边安排L,其中e∈E(G)为G的任意一条边,如果G都是L-边可选择的,那么就称图G是k-边可选择的.使图G是k-边可选择的最小正整数κ称为图G的列表边色数,记作χ′l(G).类似地,我们可以给出图G的列表色数χl(G)和列表全色数χ″l(G),它们分别是把上述边染色换为对图G的顶点或者顶点和边进行染色.从上述定义中我们马上可以得到下列关系X’l(G)≥x’(G)≥△,X”l(G)≥X”(G)≥△+1.本文主要讨论了平面图的列表染色.主要结论有：定理9假设G是最大为△(G)≥8的平面图.如果3圈与k圈不相邻k∈{4,5),那么χ′l(G)=△且χ″l(G)=△+1.本文讨论的最后一个问题是无圈全染色.一个图G的正常全染色被称为无圈全染色,如果它能够使得G中的每个圈所关联的点或边上至少出现4种颜色.图G的无圈全色数χ″a(G)是使得图G存在一个无圈全染色的最小正整数k.无圈全染色问题是由孙向勇、吴建良提出,并给出以下猜想：对任意图G,△(G)+1≤X”α(G)≤△(G)+2.本文研究了平面图的无圈全染色.我们给出了有关上述猜想的的主要结果：定理10假设G是最大度为△≥6的平面图.如果3-圈与4-圈不相交,那么它的无圈全色数χ″a(G)≤△+2.定理11假设G是最大度为△≥7的平面图.如果3-圈与3-圈不相交,那么它的无圈全色数χ″a(G)≤△+2.定理12假设G是最大度为△≥7的平面图.如果短圈i-圈与j-圈(i≠j)不相邻,那么它的无圈全色数χ″a(G)≤△+2.定理13如果G是最大度为△≥9的平面图,那么它的无圈全色数χ″a(G)≤△+2.
【作者】王兵；
【导师】吴建良；
【作者基本信息】山东大学，运筹学与控制论，2014，博士
【关键词】平面图；全染色；列表染色；无圈全染色；圈；

【参考文献】
[1]原清青.我国小额信贷市场发展研究[D].山西财经大学,金融学,2013,硕士.
[2]王其兵,李凌浩,刘先华,贺金生.内蒙古锡林河流域草原土壤有机碳及氮素的空间异质性分析[J].植物生态学报,1998,05:26-31.
[3]谢娜.潮湿环境下古文化遗址保护措施研究[D].兰州大学,环境工程,2013,硕士.
[4]胡月.接受理论指导下英语儿童文学“童趣”汉译的策略探讨[D].北京外国语大学,英语语言文学,2013,硕士.
[5]邢琼月.中国英语学习者词汇冗余现象研究[D].广东外语外贸大学,外国语言学及应用语言学,2013,硕士.
[6]周勇狄.长大公路隧道火灾数值模拟及逃生研究[D].长安大学,2006.
[7]伊优男.目标定向理论的应用对高校学生太极拳运动动机影响的实验研究[D].东北师范大学,体育（专业学位）,2012,硕士.
[8]慕福楠.面向微博用户的推荐多样性研究[D].哈尔滨工业大学,计算机科学与技术,2013,硕士.
[9]谢洪明,罗惠玲,王成,李新春.学习、创新与核心能力:机制和路径[J].经济研究,2007,02:59-70.
[10]张嘉桐.对西语翻译教学的几点思考[D].吉林大学,西班牙语语言文学,2013,硕士.
[11]陈海宽.国际运输与我国交通运输业[J].世界贸易组织动态与研究.1998(03)
[12]王电钢.几种新兴的计算机技术及其在电力企业中的应用[J].重庆电力高等专科学校学报,2003,04:44-48.
[13]黄清.不同消息源在社交媒体中的风险传播策略及其可信度研究[D].浙江大学,传播学,2013,硕士.
[14]葛付伟.RFID系统开发及通信安全性研究[D].天津大学,软件工程,2013,硕士.
[15]周莹莹.电视公益广告的纪实叙事策略探析[D].苏州大学,新闻学（专业学位）,2014,硕士.
[16]王富斌.犯罪现场重建问题研究[D].甘肃政法学院,诉讼法学,2011,硕士.
[17]王波.语料库辅助下的图式法在大学英语写作教学中的应用[D].沈阳师范大学,课程与教学论,2013,硕士.
[18]常英红.视锐5超声引导下MST行PICC置管导针器分离时机的研究与应用[D].青岛大学,护理学,2013,硕士.
[19]胡争飞.诗歌教学的语感问题探讨[D].华中师范大学,学科教学,2014,硕士.
[20]王立新.并购中的人力资源管理整合[D].电子科技大学,高级管理人员工商管理（EMBA）（专业学位）,2012,硕士.
[21]宣勇,张鹏.论创业型大学的价值取向[J].教育研究,2012,04:43-49.
[22]陈晓瑛.高等院校数学实验教学的理论研究与实践[D].湖南师范大学,2004.
[23]付金丹.一拖燃油喷射有限公司营销策略研究[D].河南科技大学,工商管理（专业学位）,2012,硕士.
[24]何立鹏.Fe（Ⅱ）超分子刷囊泡及其融合现象的研究[D].兰州大学,无机化学,2013,硕士.
[25]郭庆来,孙宏斌,张伯明,李钦,刘崇茹,李尹,杨志新,王小英,李海峰.江苏电网AVC主站系统的研究和实现[J].电力系统自动化,2004,22:83-87.
[26]李小霞.我国企业应收账款管理研究[D].北京交通大学,2010.
[27]袁林坡.N_2O的催化还原分解方法研究[D].北京化工大学,化学工程与技术,2013,硕士.
[28]蔡圣义,何勇.工件从大到小到达的带处理器费用的半在线调度算法[J].自动化学报,2003,06:917-921.
[29]徐伟华.有限群极大子群的h-完备与θ-完备[D].广西大学,基础数学,2004,硕士.
[30]甘久航.试论屏南木拱廊桥的文化生态保护[D].中国艺术研究院,艺术学理论,2013,硕士.
[31]何玉财.氰降解菌株的筛选及其固定化的研究[D].广西大学,化学工艺,2004,硕士.
[32]郑梅娟.甲状腺结节超声征象分级评估与报告系统的临床研究[D].福建医科大学,影像医学与核医学,2014,硕士.
[33]汤建燕.ASPP2基因及其甲基化在胃癌细胞中的表达及调节的探讨[D].苏州大学,普外科,2013,硕士.
[34]葛召炎.汽车发动机的变结构控制和智能控制方法研究[D].湖南大学,2003.
[35]秦伟皓.电动葫芦能源利用效率测算方法研究[D].上海交通大学,机械设计与理论,2014,硕士.
[36]刘金铎.坡面侵蚀过程及其微地形演变的试验和元胞模拟研究[D].华北水利水电学院,水力学及河流动力学,2012,硕士.
[37]王娜.两种膀胱扩大术治疗小儿神经源性膀胱22例临床疗效观察[D].山东大学,临床医学（专业学位）,2013,硕士.
[38]杨晓玲.传感网支持下视频变化检测服务研究[D].上海大学,信号与信息处理,2014,硕士.
[39]马勇.丹红注射液防治小腿皮神经营养血管皮瓣术后血管危象的临床研究[D].福建中医药大学,中医骨伤科学（专业学位）,2014,硕士.
[40]朱宏泽.基于移动社交平台的网页游戏的设计与实现[D].北京交通大学,2013.
[41]陶然.小批量轿车生产准备方法研究[D].吉林大学,机械工程,2012,硕士.
[42]潘贞存,张慧芬,张帆,桑在中.信号注入式接地选线定位保护的分析与改进[J].电力系统自动化,2007,04:71-75.
[43]徐新龙,周译玄,李家源,祁媚,任兆玉,白晋涛.石墨烯及其衍生物的太赫兹时域光谱研究[A].中国物理学会光散射专业委员会.第十七届全国光散射学术会议摘要文集[C].中国物理学会光散射专业委员会:,2013:1.
[44]王红岩.体节发生相关通路的系统生物学建模研究[D].东北师范大学,细胞生物学,2014,博士.
[45]邹礼见.内容分发网络互联的请求路由策略研究[D].华中科技大学,通信与信息系统,2013,硕士.
[46]龚正炉.基于随机骨料模型的混凝土性能多尺度数值模拟研究[D].浙江大学,结构工程,2013,硕士.
[47]冯晨晨.低氧诱导因子1α与系统性红斑狼疮相关性的分子流行病学研究[D].安徽医科大学,流行病与卫生统计学,2014,博士.
[48]陈侃.应用于UHF RFID数字基带的可变时钟技术研究[D].西安电子科技大学,微电子学与固体电子学,2011,硕士.
[49]顾倩.大型火电再热机组性能计算模型研究[D].东南大学,2005.
[50]胡飞飞.江苏省典型铅酸蓄电池企业职业危害现状及对周边环境影响调查[D].南京医科大学,劳动卫生与环境卫生学,2013,硕士.