共查询到20条相似文献,搜索用时 31 毫秒
1.
图的关联着色是从关联集到颜色集的一个映射,使得关联集中任何两个相邻的关联都具有不同的像.确定了Meredith图的关联色数,证明了对任意系列平行图都存在一个(Δ 2,2)-关联着色. 相似文献
2.
3.
路与完全图的笛卡尔积图和广义图K(n,m)的关联色数 总被引:4,自引:0,他引:4
Richrd A.Brualdi和J.Quinn Massey在[1]中引入了图的关联着色概念,并且提出了关联着色猜想,即每一个图G都可以用△(G)+2种色正常关联着色.B.Guiduli[2]说明关联着色的概念是I.Algor和N.Alon[3]提出的有向星荫度的一个特殊情况,并证实[1]的关联着色猜想是错的,给出图G的关联色数的一个新的上界是△(G)+O(Log(△G)).[4]确定了某些特殊图类的关联色数.本文给出了路和完全图的笛卡尔积图的关联色数,而且利用此结果又确定了完全图Kn的广义图K(n,m)的关联色数. 相似文献
4.
5.
6.
本文给出了路与路,路与圈的卡氏乘积图的关联着色数的完整刻画.对于圈与圈的卡氏乘积图的情形,也给出了其关联着色数的上界为乘积图的最大度加三,并且又给出了几类其关联着色数小于其最大度加三的圈与圈的卡氏乘积图类. 相似文献
7.
8.
图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类. 相似文献
9.
10.
11.
12.
13.
通过引进Mycielski图点集的一类特殊划分,利用该划分在Mycielski图循环着色中的特点改进了如下猜想:完全图的Mycielski图的循环色数等于它的点色数. 相似文献
14.
三类笛卡尔积图的关联色数 总被引:2,自引:0,他引:2
图的关联色数的概念是 Brualdi和 Massey于 1 993年引入的 ,它同图的强色指数有密切的关系 .Guiduli[2 ] 说明关联色数是有向星萌度的一个特殊情况 ,迄今仅确定了某些特殊图类的关联色数 .本文给出了完全图与完全图、圈与完全图、圈与圈的笛卡尔积图的关联色数。 相似文献
15.
对图着色问题的最大最小蚁群算法进行了改进,测试结果表明算法有效可行.在此基础上,分别设计了求解图条件着色和标号问题的相应蚁群优化算法,并对中国地图的条件着色、三正则图的条件着色、广义Petersen图的条件着色和标号问题进行了求解优化,改进和完善了目前理论研究的结论. 相似文献
16.
消去图、覆盖图和均匀图的若干结果 总被引:2,自引:0,他引:2
设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献
17.
18.
研究了双星图的IC-着色问题,得到了双星图极大IC-着色的一些必要条件.利用这些必要条件,得到了双星图的极大IC-着色至多有两类着色方案,并确定了双星图在其中一种情况下的IC-指数. 相似文献
19.
对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d. 相似文献