论文部分内容阅读
由于现实世界中诸多问题(比如药品仓库储存问题,交通灯设置问题,任务安排问题等)都可以用图的染色模型表示,所以相关的理论与方法研究一直以来都是图论的研究热点之一.现代信息科学与技术、计算机科学与技术、通信工程、交通工程等的发展和应用,为图的染色提出了一些新的研究对象,同时也为图的染色研究提供了工具和手段,诞生出了许多新的染色方法与染色理论,使得图的染色领域不断的拓宽.在图的染色方面,除了经典的点染色、边染色外,人们又提出了动态染色、条件染色、距离染色、无圈边染色、分数染色、邻强边染色、均匀染色等等.本文主要研究若干图类的均匀邻强边染色问题.
所谓图G的均匀邻强边染色是指在图的正常边染色f的基础上,满足:对任意uv∈E(G)有c(u))≠c(v)(其中,c(u)={f(uv)|uv∈E(G)}).,且每种颜色所染颜色次数之差不超过1.本文根据一些图类的特性,研究了相关图的邻强边染色问题,计算出了相应的均匀邻强边染色数,并给出了具体的染色方案.主要结果有:
(1)轮图Wn、圈Cn、风车图Kt3、Dm,n均匀邻强边染色数分别为:χeas(Wn)={5, n=44, n=5,n, n≥6χeas(Cn)={3, n≡0(mod3)4,n≡1,2(mod3),且n≠5,5, n=5χeas(Kt3)=2t,χeas(Dm,n)=2m.(2)空图与路径的联图Om∨Pn、星与完全等二部图的联图Sm∨Kn,n以及广义的θ-图θk(u,v)的均匀邻强边染色数分别为:χeas(Om∨Pm)=△(Om∨Pn)+1(m≥4,n≥4),χeas(Sm∨Kn,n)=△(Sm∨K1.1)+1, m≥2,n=1△(S2∨Kn,n), m=2,n≥2,△(S∨Kn,n), m=nχeas(θk)={k, uv(∈)E(θk(u,v))k+1,uv∈E(θk(u,v))