共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
《数学的实践与认识》2013,(16)
图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的颜色数.1965年,Vizing证明了任意最大度为△的图的边色数或者是△或者是△+1.若G是连通的,且G的每一条边e均有X′(G-e)相似文献
3.
4.
5.
一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”. 相似文献
6.
图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的双圈图类. 相似文献
7.
对于一个图G的正常边着色,如果此种边着色使得该图没有2—色的圈,那么这种边着色被称为是G的无圈边着色.用d(G)表示图G的无圈边色数,即G的无圈边着色中所使用的最小颜色数.Alon N,Sadakov B and Zaks A在[1]中有如下结果:对于围长至少是2000△(G)log△(G)的图G,有d(G)≤△ 2,其中△是图G的最大度.我们改进了这个结果,得到了如下结论:对于围长至少是700△(G)log△(G)的图G,有d(G)≤△ 2. 相似文献
8.
9.
图G的一个无圈边着色是一个正常的边着色且不含双色的圈.图G的无圈边色数是图G的无圈边着色中所用色数的最小者.本文用反证法得到了不含5-圈的平面图G的无圈边色数的一个上界. 相似文献
10.
11.
本文介绍了边对策着色,讨论了图G的边对策着色的性质.对几种特殊图类进行了讨论,分别确定链图,圈图及与圈有关的图,扇图,Petersen图的边对策色数. 相似文献
12.
给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ'(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G) < 3并且Δ≤4,那么χ'(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ'(1,0)(G)≤3Δ-1。 相似文献
13.
假定G是一个非平凡的连通图,对G的边全部着上颜色,相邻的边可以着相同的颜色.用数字表示颜色,并假定c:E(G)→{1,2,…,k,k∈N}是G的一种着色方式.G中的一条道路P称为是一条彩虹路,如果P所经过的边的颜色各不相同.如果图G的任意两点间都有一条彩虹路,则称G是彩虹路连通的.使得图G为彩虹路连通所使用的最少颜色数k称为G的彩虹路连通数.本文计算了线性多边形链图的彩虹路2~连通度和线性偶数边多边形链图的彩虹路连通数. 相似文献
14.
15.
强色指数的一个新的上界 总被引:1,自引:0,他引:1
给出了图的强色指数的一个新的上界,并指出几类恰好达到该上界的图,从而改进了Erodoes和Nesetri的强色指数猜想,在某种意义上证明了这个猜想。 相似文献
16.
已经知道双星图至多有两种极大IC-着色,并且其中一种情况下的IC-指数已经确定.在此基础上,研究了双星图的的另一种极大IC-着色,得到了在这种情况下的IC-指数.从而得到了双星图的所有极大IC-着色,且双星图的IC-指数为:M(DS(m,n))=(2(m-1)+1)(2(m-1)+1)(2(n-1)+1),其中2≤m≤n. 相似文献
17.
研究了双星图的IC-着色问题,得到了双星图极大IC-着色的一些必要条件.利用这些必要条件,得到了双星图的极大IC-着色至多有两类着色方案,并确定了双星图在其中一种情况下的IC-指数. 相似文献
18.
19.
简单图G的一个一般边染色是指若干种颜色关于图G的所有边的一个分配,不要求相邻的边被分配不同的颜色.设f是G的使用了k种颜色的一般边染色,若对(?)u,v∈V(G),u≠v,都有与u关联的边的颜色构成的多重集合异于与v关联的边的颜色构成的多重集合,那么称f是使用了k种颜色的顶点被多重色集合可区别的一般边染色.对G进行顶点被多重色集合可区别的一般边染色所需的最少颜色数记为c(G),并且称c(G)为图G的顶点被多重色集合可区别的一般边色数.本文确定了m个C_4的点不交的并mC_4的顶点被多重色集合可区别的一般边色数. 相似文献
20.
杨随义 《数学的实践与认识》2016,(10):152-161
图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.应用构造具体染色的方法给出了路与星、扇、轮图的积图的邻点可区别I-全色数 相似文献