色的概念。
目前已证明,图的均匀边色数等于它的正常边色数(即苁’(G)=Z’(G))。
而经过多年的研究,图的正常边染色理论研究已趋于成熟和完善,有著名的Vizing定理:若G是简单图,则一定有Z’(63=A(63或Z’(G)=△(回+1.。
从而对于图的均匀边染色研究等同于图的正常边染色研究,只要考虑什么图属于第一类,什么图属于第二类就可以了。
1.3图的均匀全着色的研究动态 1994年,Hunglintl9】最早给出了图的均匀全着色和均匀全色数的概念。
1996年,张忠辅在天津南开大学数学研究所“组合数学与图轮”学术会议上作学术报告时也独立地 大连理丁大学硕士学位论文提出了这些概念。
他们在研究了一些简单图的均匀全色数后提出了均匀全着色猜想:任意简单图的均匀全色数至多为A(G)+2,且以。
(G)=Z。
(G)。
自此揭开了图的均匀全着色研究的序幕。
Hunglintl91首先研究了图的均匀全着色,并提出了下面的猜想:给定图G,若七≥{‖(G),A(G)+2},则图G有一个瑚匀全着色。
并证明了这个猜想对一些特殊图类是成立的,例如树,完全图,完全二部图,A(G)≥ly(G)|-2的图等。
同时,他注意到存在许多满足全着色数Z。
(G)=△(G)+l却不能△(G)+l均匀全染的图G. 在此基础上,王维凡提出了如下猜想:对于图G,有彤(G)≤△(G)+2。
此猜想与著名的提出的著名的全着色猜想统一了起来。
他还研究了树、完全二部图、完全多部图以及△(G)≤3的无环多重图的均匀全着色,证实了在这些情况下上面的均匀全着色猜想成立。
图的均匀着色应该算是一个比较新的概念,从提出至今也不过发展了10几年,才刚刚起步,因此重大成果并不是太多。
目前已知的结论如下〔20-26】: 对于图G的口-图的均匀全着色猜想成立,即:对0-图G有Z(G)=z。
(G)=4:“ 对完全二部图如‖有Z(G)=max{m,栉)+1+万(聊,功,其中万(聊,刀)(m,n)是图的Kronecker函数。
广义等星图G,Z(G)=n+1. 轮图的均匀全色数:: 彤(形)=刀=△(%)+1. 扇图的均匀全色数: Z(E)=n----△(E)+1. 完全图的均匀全色数: 抛,={会:臻≯ 星图的均匀全色数: 以c白,开,={会:≥::三:, 对于图的Mycielski图的均匀全着色问题,已研究了路、星、轮扇等图的Mycielski图的均匀全色数,主要结果有:Z(M(只))=△(M(只))+l;彤(M(鼠))=△(M(瓯))+l (刀≥2);Z(M(形))=袱M(C))=2n+l(刀≥3). C二3G和JpooG的均匀全着色 对于简单图G,若△(G):爿y(G)l_l,且G仅有一个最大度点,则‖(G)=△(G)+l。
这是Z(G)=△(G)+l的一个充分条件。
由此条件可得到了一些『一阶简单图的联图的均匀全色数。
两条路径的联图: 胪l, f3, Z(仇VP。
)={5, 刀=2, b+3,n>3. 路径与圈的联图: Z(£Ve)=刀+4, 眨3. 两个圈的联图: ‖(q VCn)=刀+4, n>3. 路径与星图的联图:彤(只V K。
.。
)=2n+l, 蹦. 路径与扇图的联图:Z(£VC)=2n+l, 眨3. 圈与扇图的联图: ‖(e V E)=2n+l,,幽. 路径与轮图的联图:Z(只V既)=2n+l,,西. 圈与轮图的联图: Z(e V形)=2n 4-l,,西. 简单图G和日中,若A(G)爿V(G)I_l(或A(H)={V(H)I-I),Iq(IV(G)I+I坎豳))=l(mod 2),则Z(GVH)=I坎回I 4-I V(H)I。
此结论可以推广到多个图的联图,即对于简单图Gl,G2,……,G,,存在九∈{l,2,……,,>.使得△(q)=爿y(g)l+l且ly(V:。
q)l-∑2。
Iy(Gj)1.1(mod2),则Z(V:。
G)=∑r=。
1y(G)I。
简单图G和日中,若A(G)爿V(G)I-1,A(H)q y(日)f-2,且G只有一个最大度点,则Z(GV均=I坎回I 4-IV(H)I。
对于简单图G,若△(G)爿矿(G)I-l,且I坎回i=1(mod2),则Z(G)=△(G)+l。
对于简单图G,若△(G)爿y(G)I-2,则Z(G)<lV(G)l。
设£是刀阶路径,k是自然数,当且仅当两顶点距离为吠V,■)=七时添加边U■,所得到的图称为露。
当以≥2k+l,it/≥5时Z(露)=5=△+2.
上一篇:
信息系统对企业战略和竞争优势的作用毕业论文
下一篇:
让我掉下眼泪的