图的无圈边染色

【摘要】设G=(UE)是一个简单图,其中V和E分别表示G的点集和边集.令△和g(G)分别表示G的最大度和围长.如果能将图G画在平面上,使得它的边仅在其端点处相交,则称G是可平面图.图的这种平面上的画法称为图的平面嵌入,称为平面图.图G的一个正常k-边染色是指映射c：E(G)→{1,2,…,k}使得相邻的边染不同的颜色.如果G有一个k-边染色,我们就说图G是k-边可染的.边色数χ’(G)是指使得图G是k-边可染的最小正整数k.无圈k-边染色是指图G的一个正常的k-边染色,使得不产生双色圈,即染任意两种颜色的边导出子图是森林.图G的无圈边色数a’(G)是指使得图G有无圈k-边染色的最小正整数k.1978年Fiamcik最早提出了无圈边染色和无圈边色数的概念.1991年,Alon等人运用概率方法率先证得了图的无圈边色数的一个线性上界,即对任何图G有a’(G)≤64Δ.Molly和Reed(1998)将其改进到a’(G)≤16△.对于围长有所限制的图Muthu等人(2005)证明了当g(G)≥220时,a’(G)≤4.52△.2013年Esperet和Parreau证得了对任何图G,a’(G)≤4△一4.这也是迄今为止,关于一般图的上界的最好的一个结果Fiamcik和Alon等人分别于1978年和2001年先后提出了以下著名的无圈边染色猜想(简称AECC):猜想(AECC):对任意图G,有a’(G)≤Δ+2.这个猜想至今仍未得到证实,仅知道一些特殊图类满足该猜想,比如立方图,最大度至多为4的非4-正则图,2-退化图,g(G)≥5的可平面图,不含4-,5-圈、或不含4-6-圈的可平面图.本学位论文在前人工作的基础上,进一步研究了图的无圈边染色问题,共分5章.在第一章,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.同时,给出了无圈边色数的几个特征性质引理.在第二章,我们研究了4-正则图的无圈边染色,证明了：若G是4-正则图,则a’(G)≤6,从而彻底解决了Basavaraju等人在[Acyclicedgecoloringofgraphswithmaximumdegree4.J.GraphTheory,2009,61(3):192-209]一文中遗留下来的一个问题.结合已有的相关结论,即得：对于最大度至多为4的图,无圈边染色猜想是成立的.在第三章,我们研究了一般平面图的无圈边染色,证明了：若G是可平面图,则a’(G)≤△+7.这个结果改进了Basavaraju等人在[Acyclicedge-coloringofplanargraphs.SIAMJ.DiscreteMath.,2011,25(2):463-478]一文中得到的结论a’(G)≤△+12.同时,△+7仍是迄今为止平面图的无圈边色数的最好的一个上界.在第四章,我们研究了不含特殊短圈的平面图的无圈边染色,得到了无圈边染色猜想成立的几个充分条件,证明了：若G是不含i-圈的可平面图,其中i∈{3,4,5,6},则a’(G)≤△+2.特别的,我们证明了：设G是可平面图.若G不含i-圈,i∈{4,5},或不含3-圈和6-圈相邻,则a’(G)≤△+2.这在一定程度上改进了诸多已有的相关结果.在第五章,我们研究了外可平面图的无圈边染色,证明了任意一个△≥5的外可平面图均是无圈△-边可染的,实际上,我们证明了：若G是一个外可平面图且△≥5,则a’list(G)=△,其中a’list(G)表示G的无圈列表边色数.因△不能降至3或4,该结论是最好的.对于△=4的外可平面图,我们给出了一个使得其恰是无圈4-边可染的一个充分条件.同时,我们也说明了存在无限多个外可平面图使得△=4且a’list(G)=a’(G)=5.
【作者】舒巧君；
【导师】王维凡；
【作者基本信息】苏州大学，运筹学与控制论，2014，博士
【关键词】图；平面图；最大度；无圈边染色；无圈列表边染色；外可平面图；

【参考文献】
[1]戴庆炎.嵌入式系统开发平台的设计与实现[D].吉林大学,软件工程,2014,硕士.
[2]王鹏帅.级联型多电平逆变器拓扑及其调制策略研究[D].太原科技大学,电力电子与电力传动,2013,硕士.
[3]黄琳.耶氏酵母POX5基因的改造及其对γ-癸内酯产量的影响[D].天津科技大学,生物化学与分子生物学,2010,硕士.
[4]孙翠骥.去铁蛋白双金簇可控自组装及其生物医学成像的研究[D].吉林大学,2011.
[5]许英.区域连锁超市供应链差异化研究[D].上海交通大学,工商管理,2013,硕士.
[6]李艳君.我国缺陷食品侵权救济制度研究[D].华东交通大学,民商法学,2013,硕士.
[7]于承敏.数据挖掘(DataMining)技术运用于教育领域之探讨[J].聊城大学学报(自然科学版),2005,02:79-82.
[8]华杭菊.膈下逐瘀汤逆转裸鼠移植瘤MDR-1的实验研究及逆转复发转移大肠癌MDR-1的临床研究[D].福建中医药大学,中西医结合临床（专业学位）,2013,硕士.
[9]王丽丽.大学生FOK判断影响因素的实验研究[D].辽宁师范大学,发展与教育心理学,2011,硕士.
[10]郑石军.基于贝叶斯网络的数据图检索算法研究[D].大连海事大学,计算机科学与技术,2013,硕士.
[11]黄淑演.超声造影与增强磁共振对超声BI-RADS 4B级乳腺肿块诊断价值的对比研究[D].复旦大学,临床医学（专业学位）,2013,博士.
[12]李林程聪红.影响用电量与经济增长关系的因素分析[J].商,,28:.
[13]骆呈军.土工布力学性能的模拟及应用研究[D].青岛大学,纺织工程,2004,硕士.
[14]季田田.核电站松动件定位分析与质量估计系统及其LabVIEW实现[D].杭州电子科技大学,检测技术与自动化装置制,2014,硕士.
[15]汪悦.教育学硕士研究生学业生涯规划的现状研究[D].华中师范大学,教育经济与管理,2013,硕士.
[16]翟瑞国.载钛膨胀石墨在油水体系中对油的吸附性能研究[D].天津大学,2012.
[17]刘威宏.基于行政法角度的城市管理综合执法实践的理论及其对策研究[D].天津大学,公共管理,2013,硕士.
[18]唐友明.媒介影响下的政策议程设置模式论[D].安徽大学,新闻与传播,2013,硕士.
[19]郭春兰.枯草芽孢杆菌21的分离及其抑菌能力研究[D].黑龙江八一农垦大学,生物化学与分子生物学,2014,硕士.
[20]张红军,沈阳.陆上盐丘成像技术研究[J].石油地球物理勘探,2003,S1:47-51+138.
[21]曾志敏,李乐.论公共理性决策模型的理论构建[J].公共管理学报,2014,02:1-12+15+139.
[22]邱爱兵,文成林,姜斌.基于混杂系统方法的一类采样数据系统鲁棒故障检测(英文)[J].自动化学报,2010,08:1182-1188.
[23]翟帅帅.胶东半岛地区残疾人体育健身服务体系的构建与实践研究[D].鲁东大学,体育教育训练学,2013,硕士.
[24]王贵贤.淫羊藿苷在磨损颗粒诱导破骨细胞活化中的作用[D].苏州大学,骨外科学,2013,硕士.
[25]王阳.穿墙探测成像研究[D].西安电子科技大学,信号与信息处理,2012,硕士.
[26]朱雷坚.基于Android的实时语音通信系统的设计与实现[D].浙江工业大学,2013.
[27]彭新龙.封装膜用交联POE的老化性能研究[D].广东工业大学,高分子化学与物理,2013,硕士.
[28]彭婧孜.论19世纪法国空想社会主义的社会建设思想[D].浙江工商大学,马克思主义基本原理,2013,硕士.
[29]白艳玲.非内分泌科临床护士胰岛素注射相关知识调查分析及对策[D].吉林大学,护理学,2014,硕士.
[30]关竹君.穴位埋线配合艾灸神阙穴治疗原发性痛经的临床研究[D].广州中医药大学,针灸推拿学,2014,博士.
[31]张文军,陶阳,屠莉娅,何珊云.一场关于“课程”的复杂会话——“课程意识、课程建构与课程能力建设国际研讨会”综述[J].教育发展研究,2015,04:80-84.
[32]记者张亦筑.国内首片15英寸单层石墨烯在渝问世[N].重庆日报,2013-01-23009.
[33]李刚,王扬渝,文东辉.水合抛光加工的运动学特性[J].机械工程学报.
[34]牛彦斌.地理信息系统支持下的耕地地力等级划分[D].河北农业大学,土壤学,2004,硕士.
[35]陈瑜.胃癌MG7-Ag模拟表位为基础构建多表位联合的基因疫苗的研究[D].第四军医大学,内科学,2004,硕士.
[36]张玲.误差相关的半变系数模型的估计[D].兰州理工大学,运筹学与控制论,2013,硕士.
[37]杜安郑.论我国判例制度之构建[D].郑州大学,诉讼法学,2013,硕士.
[38]杨传光.城市道路横断面设计问题研究[D].长安大学,交通运输工程（专业学位）,2013,硕士.
[39]董健康.面向数字校园的信息系统集成构架[J].甘肃政法成人教育学院学报,2005,04:171-172.
[40]范莹莹.陕西省土地违法治理对策研究[D].长安大学,土地资源管理,2013,硕士.
[41]孙一民,陈远生.母线保护装置的IEC61850信息模型[J].电力系统自动化,2007,02:51-54.
[42]朱军.三维混合网格生成与N-S方程求解[D].西北工业大学,飞行器设计,2004,硕士.
[43]张楠.潍坊市滨海新区水系景观规划研究[D].山东大学,建筑与土木工程,2012,硕士.
[44]曾建彬.试析1757-1813年英国东印度公司在孟加拉的土地税收政策[D].兰州大学,世界史,2013,硕士.
[45]井祥鹤.陆路物流物资配载及输送路径优化问题的模型与算法[D].南京理工大学,2007.
[46]刘晓晶.生态翻译学视角下的林戊荪《孙子兵法》英译研究[D].苏州大学,翻译,2013,硕士.
[47]司马则茜.带利率的风险模型的破产问题[D].曲阜师范大学,概率论与数理统计,2004,硕士.
[48]贾明武.蜂窝电话用锂离子电池标准分析对比[J].电子质量.2001(04)
[49]杨磊.矿质元素对半夏生长和品质的影响研究[D].南京农业大学,中药学,2009,硕士.
[50]王冲冲.基于高精度计算机视觉的刀具磨损在位检测[D].东华大学,机械制造及其自动化,2014,硕士.