论文部分内容阅读
设G=(V,E)是一个简单图,其中V和五分别表示G的点集和边集.令A和g(G)分别表示G的最大度和围长.如果能将图G画在平面上,使得它的边仅在其端点处相交,则称G是可平面图.图的这种平面上的画法称为图的平面嵌入,称为平面图. 图G的一个正常fc-边染色是指映射E(G)—{1,2,...,k}使得相邻的边染不同的颜色.如果G有一个I边染色,我们就说图G是I边可染的.边色数x(G)是指使得图G是I边可染的最小正整数L无圏I边染色是指图G的一个正常的k-边染色,使得不产生双色圏,即染任意两种颜色的边导出子图是森林.图G的无圏边色数a(G)是指使得图G有无圏k-边染色的最小正整数k. 1978年,Kam她最早提出了无圏边染色和无圏边色数的概念.1991年,Alon等人运用概率方法率先证得了图的无圏边色数的一个线性上界,即对任何图G有Y(G)<64A.Molly和Reed(1998)将其改进到a(G)<16A.对于围长有所限制的图,Muthu等人(2005)证明了当g(G)>220时,af(G)<4.52A.2013年,Esperet和Parreau证得了对任何图G,af(G)<4A-4.这也是迄今为止,关于一般图的上界的最好的一个结果.Kam过k和Alon等人分别于1978年和2001年先后提出了以下著名的无圏边染色猜想(简称AECC): 猜想(AECC):对任意图G,有a(G)5的可平面图,不含4-,5-圏、或不含4-,6-圏的可平面图. 本学位论文在前人工作的基础上,进一步研究了图的无圏边染色问题,共分5章. 在第一章,我们给出所用到的基本概念,简述了相关领域的研究现状并呈现了本文的主要研究结果.同时,给出了无圏边色数的几个特征性质引理. 在第二章,我们研究了4-正则图的无圏边染色,证明了:若G是4-正则图,则a(G)<6,从而彻底解决了Basavaraju等人在[Acyclic edge coloring of graphs with maximum degree4.J.Graph Theory,2009,61(3):192-209]—文中遗留下来的一个问题.结合已有的相关结论,即得:对于最大度至多为4的图,无圏边染色猜想是成立的. 在第三章,我们研究了一般平面图的无圏边染色,证明了:若G是可平面图,则a(G)5的外可平面图均是无圏A-边可染的,实际上,我们证明了:若G是一个外可平面图且A>5,则a(ist(G)=A,其中a丨ist(G)表示G的无圏列表边色数.因A不能降至3或4,该结论是最好的.对于A=4的外可平面图,我们给出了一个使得其恰是无圏4-边可染的一个充分条件.同时,我们也说明了存在无限多个外可平面图使得A=4且aIist(G)=a(G)=5。