亚Hamilton图的四线染色和Fulkerson染色.pdf

《亚Hamilton图的四线染色和Fulkerson染色.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中圈料孽敢求尖誊硕士学位论又亚Hamilton图的四线染色作者姓名：学科专业：导师姓名：完成时间：和Fulkerson染色陆晓明应用数学侯新民副教授二O一二年五月UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeFanocoloringsandFulkersoncoloringofHypohamiltoniangraphAuthor’SName：XiaomingLuSpeciality：AppliedMathematicsSupervisor：AssociateProf．XinmingHouFinis

2、hedTime：May．2012中国科学技术大学学位论文原创性声明本人声19抑i呈交的学位论文，是本人在导师指导下进行研究。f：作所取得的成果。除已特别加以标注雨I致谢的地方外?论文中不包含任何他人已经发表或撰写过的研究成果。与我一一同工作的同志对本研究所做的贡献均已在论文cl。作了l列确的说明。作者签名：签字同期：塑!兰垒6图!璺f中国科学技术大学学位论文授权使用声明作为申请学位的条什之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库

3、》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。

4、回公开口保密年作者签名：逝麴签字日期：翩签名：毖函签字曰势j：星!!!茎!塑竺皇：{录目录同录．⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯I摘要．⋯⋯．⋯⋯．⋯⋯．．．⋯⋯⋯．⋯⋯⋯⋯⋯·⋯⋯⋯··IIIABSTRACT。．。．．．．．．．．．．．．．．．。．．．．。．．．．．．．．．．．．．．．．．-．一．-．-一··-．·V第1章绪论⋯，．．．．．⋯．．⋯，．．⋯⋯，⋯⋯⋯-⋯．⋯⋯⋯-tl1．1图沦概述．⋯．．．⋯⋯-⋯．

5、．⋯．-··⋯⋯-⋯··⋯·⋯r-⋯·l1．2图论基本概念．⋯⋯．⋯⋯．．⋯．．．⋯⋯．⋯⋯·⋯··⋯⋯2第2章亚Hamilton图的四线染色⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··92．1染色的基本概念的介绍⋯⋯．⋯．．．．⋯-．··⋯-·⋯·-····⋯·92．2关于整数流和图的圈覆盖的现有结果．．．，。，．．，⋯e。．··．．·，···．．·102．3三正t)!lJ!,]F．Hamilton图及其四线染色⋯⋯．⋯⋯⋯-．．⋯⋯·⋯·11第3章亚Hamilton图的Fulkerson染色的研究⋯⋯⋯⋯⋯⋯．．173．1Fulkeson染色的概念以及一般图的Fulkerson染色．．⋯．⋯⋯·一．·1

6、73．2亚Hamilton图Fulkerson染色性质的研究．⋯⋯⋯．·⋯⋯····⋯·18第4章总结与展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯2l4．1总结．．．．．．．．．．．．．．．．．．．．．．．⋯⋯．·．·⋯·⋯··-····-·⋯···2I4．2展望⋯．⋯⋯⋯．⋯⋯．⋯．⋯⋯⋯·⋯⋯·⋯⋯·⋯⋯21参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯··24致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯-25原书空白页，不缺内容摘要Fulkerson袤!i-想指的是对于⋯。个无桥三正则图，一定存在六个完美匹配，使得每条边刚好落在其r№个匹配之中。这个问题困扰了人们很多年。我们知道，对于⋯个可

7、以三边染色的．铜三则蚓，结果是显而易见的；但是对_i尤浊j边染色，即只可四边染包的三正则图(我们通常称之为Snark)，结果就不那么容易给出了。所以研究SnarklJ叟,为了证FOtFulkerson猜：想的重要方法。但是对于Snarkl't',J结构，我们很难给出一个非常好的定性的描述，我们只能一类一类研究。在1994年，范更华．；

8、=tlRaspaud提出了一个弱化的猜想，即任意一个无桥三正则闰G，必定含有三个完美匹配A，l，鸠．鹏满足n，1nM2nn如=0．在2005年，EditaMacajova和lMartinSkoviera义证J刿TFan—Raspaud猜想与四线染色猜想的等

9、价性。本文就是研究一类snark-亚Itamilton图是否满足Fulkerson猜想不tlFan—raspaud猜恕，并褥到了下面三个结论：(1)．证明了丑gHamilton图是满足四线染色猜想的，从而它是满足Fan—raspaud猜想的；(2)．证明了若存在Fulkerson猜想的最小反例图G，则G的围长至少为5；(3)．给出了一类满足Fulkerson猜想的亚Hamilton阔。关键词：Fulkerson猜想，Snark，．弧