共查询到19条相似文献,搜索用时 93 毫秒
1.
王志坚 《苏州科技学院学报(自然科学版)》1994,(2)
分别以X(G)、X1(G)、X2(G)记图G之色数、边色数和全色数,对任意p阶简单图G及其补图G,本文得到以下Nordhaus-Gaddum型结论:本文还指出,上面所有下界、上界对每个正整数p均可达到。 相似文献
2.
许宝刚 《山东大学学报(理学版)》1995,(2)
图G的染色数X(G)是使得G中任何相邻两点均染不同色的最小颜色数.文中证明了:如果ω(G)≥6,△(G)=ω(G)+1,|V(G)|≤2ω(G)+1,则X(G)=ω(G),给出了两个图G0、G1,使得|V(G0)|=14,ω(G0)=6,△(G0)=7,X(G0)=7;|V(G1)|=11,ω(G1)=5,△(G1)=6,X(G1)=6. 相似文献
3.
许宝刚 《山东大学学报(自然科学版)》1995,30(2):156-159
图G的染色数X(G)是使得G中任何相邻两点均染不同色的最小颜色数。文中证明了,如果ω(G)≥6,△(G)=ω(G)+1,ㄧV(G)ㄧ≤2ω(G)+1,则X(G)=ω(G),给出了两个图G0,G1,使得ㄧV(G0)ㄧ=14,ω(G0)=6,△(G0)=7,X(G0)=7;ㄧV(G1)ㄧ=11,ω(G1)=5,△(G1)=6,X(G1)=6。 相似文献
4.
研究了素介完全图KP的边的n-染色,给出了计算它的子图Gp(Si)的团数的一种算法,得到2个三色,4个四色Ramsey数的新的下界。 相似文献
5.
许宝刚 《山东大学学报(理学版)》1996,(3)
图G的全色数XT(G)是使得V(G)U∪E(G)中相邻或相关联的元素均染不同颜色的最少颜色数目.如果XT(G)=△(G)+1,则记如果XT(G)=△(G)+2,则记G∈.两个图G和H的联图G∨H是一个简单图,使得V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv(G),v∈(H)}.本文证明了对任意的两个正整数m和n,Pm∨Pn∈当且仅当m=n=2或m=n=1,从而完全确定了两个路的联图的全色数. 相似文献
6.
李向东 《河北理工学院学报》1999,21(1):56-58
通过对三次图结构的研究给出了两个主要结论:(1)对连通度μ(G)=0,1,2,3,分别给出点数P=|V(G)|的可达到的下界;(2)2—连通图G,存在2—连通三次图G′,G′可收缩到G。 相似文献
7.
许宝刚 《山东大学学报(自然科学版)》1996,31(3):290-297
图G的全色数XT(G)是使得V(G)∪E(G)中相邻或相关的元素均染不同颜色的最少颜色数目。如果XT(G)=△(G)+1,则记G∈C1/T;如果XT(G)=△(G)+2,则记G∈C2/T。 相似文献
8.
9.
王志坚 《苏州科技学院学报(自然科学版)》1995,(2)
以a(G)a1(G)分别记图G的点荫度、边荫度,对任意P阶非平凡简单图G及其补图,本文得到以下Nordhaus-Gaddum类型不等式:|x|、|x|分别表x之上整数、下整数。而且,对于每一正整数p,(i)、(ii)、(iv)式下界和(iii)式上界均可达到。 相似文献
10.
该文构造了1个新的素数阶循环图,从而得到1个Ramsey数R(6,17)的下界:R(6,17)≥380。 相似文献
11.
12.
图G的圆色数xc(G)(也称为星色数)是图的色数的一种推广,给出了图的圆色数等于其色数的一些充分条件。 相似文献
13.
考虑使得图G存在无重复的k-重n-染色的所有数对(n,k),其比值n/k的下确界定义为图G的无重复分数染色数.圈图的无重复分数染色数在文献中已有研究,除了C10,C14和C17之外的所有圈图的无重复分数染色数都已被确定,讨论并给出了这3个圈图的无重复分数染色数的上下界. 相似文献
14.
给定一个平面图G,χ´l(G)和χ"l(G)分别表示图G的列表边色数和列表全色数.证明了:如果一个平面图G满足Δ(G)≥7,并且任何一个三角形至多和一个其他的三角形相邻,则有χ´l(G)≤Δ(G)+1和χ"l(G)≤Δ(G)+2成立。 相似文献
15.
田双亮 《西北民族学院学报》2005,26(2):1-3
通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图. 相似文献
16.
设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。 相似文献
17.
图上的对策着色和对策着色数 总被引:1,自引:0,他引:1
图G的对策色数Ⅱχg(G)是由图的点色数χg(G)拓展而来的.本文对几类特殊的图进行了讨论,分别给出了图Qn,Gn以及与圈有关图的对策色数Ⅱ,并给出了选手Alice相应获胜的对策. 相似文献
18.
一类距离图的分数色数 总被引:1,自引:0,他引:1
摘要:主要讨论了距离图G(Z,Dm,k,k+1,k+2,k+3)(其中Dm,k,k+1,k+2,k+3={1,2,…,m}-{k,k+1,k+2,k+3})的分数色数,以及当2k≤m≤2k+5时G(Z,Dm,k,k+1,k+2,k+3)的色数。 相似文献