星与星的联图点可区别I-全染色和点可区别VI-全染色

文章讨论Sm∨Sn的联图点可区别I(VI)-全染色,确定了当3≤m≤n≤n+2时,它们的点可区别I-全色数及点可区别VI-全色数,也说明了VDITC猜想和VDVITC猜想对这类图是成立的.

mC12的点被多重集可区别的I-全染色和VI-全染色

通过构造以多重色集合和空集为元素的矩阵,应用组合分析法及构造具体染色的方法,得到了mC12的点被多重色集合可区别的I-全染色和VI-全染色的全色数及最优染色方案。

一类正则循环图的Cartesian积图的D(β)-点可区别VI-全染色及I-全染色

设G是简单图,若图G的全染色f满足:1)(?)uv,vw∈E(G),有f(uv)≠f(vw);2)(?)uv∈E(G),u≠v,有f(u)≠f(v);3)(?)u,v∈V(G),0<d(u,v)≤β,有S(u)≠S(v),这里色集合S(u)={f(u)}∪{f(uv)|uv∈E(G)}.则称f是图G的一个D(β)-点可区别I-全染色.若f只满足条件1)和3),则称f是图G的一个D(β)-点可区别VI-全染色.研究了当β=1,2时一类正则循环图与圈的Cartesian积图的D(β)-点可区别VI-全色数和D(β)-点可区别I-全色数,并讨论了正则图的D(β)-点可区别VI-全色数和D(β)-点可区别I-全色数的上界.

单圈图的D(2)-点和可区别全染色

图G的D(2)-点和可区别全染色是指在图G的一个正常全染色φ下,G中任意两个距离不超过2的顶点u,v,其色集合中所有颜色数之和互不相同.使得G有一个k-D(2)-点和可区别全染色的最小整数k,称为图G的D(2)-点和可区别全色数.文中应用组合零点定理和权转移方法刻画了单圈图的D(2)-点和可区别全染色,并得到其D(2)-点和可区别全色数.

单圈图的邻点全和可区别全染色

用结构分析法完整刻画单圈图U的邻点全和可区别全染色,并得到当U■C_(n)且n■0(mod 3)时,ftndiΣ(U)=Δ(U)+2;其他情况下,ftndiΣ(U)=Δ(U)+1.表明邻点全和可区别全染色猜想在任意单圈图上都成立.

圈与路的点被多重集可区别的E-全染色

图G的E-全染色是指使得相邻顶点染以不同色,每条边与它的端点染以不同的颜色的全染色.设f是图G的E-全染色,图G的一个顶点x在f下的多重色集合C˜(x)是指点x的颜色以及与x关联的边的颜色构成的多重集.若图G的任意两个不同顶点在f下的多重色集合不同,则f称为图G的点被多重集可区别的E-全染色.对图G进行点被多重集可区别的E-全染色所需用的最少的颜色的数目叫做G的点被多重集可区别的E-全色数.利用反证法和构造具体染色的方法,讨论了圈与路的点被多重集可区别的E-全染色问题,给出了圈与路的最优的点被多重集可区别的E-全染色方案,并确定了圈与路的点被多重集可区别的E-全色数.

一类仙人掌图的D(2)-点可区别全染色

用数学归纳法和组合分析法给出最大度为3的仙人掌图G T的D(2)-点可区别全染色,进而得到χ_(2vt)(G T)≤6.结果表明,D(β)-VDTC猜想对最大度为3的仙人掌图成立.

三正则构造图的邻点全和可区别全染色

首先,根据Snark图的结构特点,构造基于双星和十字交叉形的两类三正则图;其次,利用穷染法和组合分析法研究四类三正则构造图的邻点全和可区别全染色问题,得到了它们的邻点全和可区别全色数均为2.

随机图的邻点可区别VI-均匀全染色算法

邻点可区别VI-均匀全染色是指图中任意两条相邻边分配不同的颜色,且任意两个色类(点或边)的颜色个数最大相差为1,同时确保相邻顶点的色集合不同,其所用的最少颜色数称为图的邻点可区别VI-均匀全色数。提出了一种针对随机图的邻点可区别VI-均匀全染色算法,该算法依据染色条件设计了三个子目标函数和一个总目标函数,并依据交换规则逐步迭代寻优,直至染色结果满足总目标函数的要求。同时给出了详细的算法执行步骤,并进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定顶点数的图的最小邻点可区别VI-均匀全色数。

点不交的m个C_3的并的点可区别全染色

利用μ(G)的定义确定了点不交的m个C3(m≥2)的并的点可区别全色数的下界,并借助矩阵给出了点不交的m个C3(m≥2)的并的点可区别全染色方法,进而确定了它的点可区别全色数.

mK_4的点可区别全染色

利用色集事先分配法,借助于矩阵构造具体染色及递归法的方法,研究图的点可区别全染色问题,给出了m个K4的点不交的并mK4的点可区别全色数χvt(mK4)的确切值,即"如果(k-1)4<4m≤(k)4,m≥2,k≥6,则χvt(mK4)=k".验证了VDTC猜想对mK4成立.

若干联图的邻点可区别I-全染色

利用函数构造法和数学归纳法,考虑图P_m∨S_n,F_m∨W_n和W_m∨W_n的邻点可区别I-全染色,给出了它们邻点可区别I-全色数.

完全二部图K_(3,n)(3≤n≤17)的点可区别E-全染色

设G是一个简单图,f为G的一个E-全染色.对任意点x∈V(G),用C(x)表示在f下点x的色以及与x关联边颜色所构成的集合.若u,v∈V(G),u≠v,有C(u)≠C(v),则f称为图G的点可区别E-全染色,简称VDET染色.图G的VDET染色所用颜色数目的最小值称为图G的点可区别E-全色数(简称为VDET色数),记为χevt(G).利用分析法和反证法,讨论并给出完全二部图K3,n(3≤n≤17)的点可区别E-全色数.

关于θ-图的邻点可区别全染色

u,v两点间连三条内部不相交的路且至多有一条长度为1的图,称为θ-图.设G是阶至少为2的连通图,k是正整数,f是V(G)∪E(G)到{1,2,3,…,k}的映射,对任意u∈V(G),记C(u)={f(u)}∪{f(uv)｜uv∈E(G),v∈V(G)}.如果:1)对任意uv,vw∈E(G)u≠w,有f(uv)≠f(vw);2)对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);3)对任意uv∈E(G),有C(u)≠C(v),那么称f为G的k-邻点可区别全染色(简记为k-AVDTC),称min{k｜G有k-邻点可区别全染色}为G的邻点可区别全色数,记作χat(G).本文得到了θ-图的邻点可区别全染色.

若干路的冠图的邻点可区别V-全染色

根据路与完全图(星、扇、轮、路、圈)构造的冠图的结构性质,应用分析和构造函数法研究了邻点可区别V-全染色,得到了路与完全图(星、扇、轮、路、圈)构造的冠图的邻点可区别V-全色数.

完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色

借助已有的完全二部图K_(2,n)和K_(3,n)的点可区别IE-全色数的结论,利用组合分析及构造具体染色的方法探讨完全二部图K_(2,n)和K_(3,n)的一般点可区别全染色问题,确定了K_(2,n)和K_(3,n)的一般点可区别全色数.

一类含有4-圈的单圈图一般点可区别全染色

设G为简单图.设f是图G的一个一般全染色,若对图G的任意两个不同的顶点u、v,有C(u)≠C(v),则称f为图G的一般点可区别全染色(简记为GVDTC).对图G进行一般点可区别全染色所需要的最少颜色数称为图G的一般点可区别全色数.将一类含有4-圈的单圈图悬挂边的染色按从小到大的顺序排列,探讨了它的一般点可区别全染色,确定了它具有一般点可区别全染色,并得到了它的一般点可区别全色数.

P_m∨P_n的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k 正常全染色f称为是邻点可区别的,如果对G的任意相邻的两顶 点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为是G的邻点可区别全色数.得到了两条路的 联图的邻点可区别全色数.

一类2维广义格子图的邻点可区别全染色

定义一类2维广义格子图H2(G,n,m;k1,k2).且通过从图的结构出发,利用构造染色的方法,得到图H2(C5,n,m;5,5)的邻点可区别全色数.

随机图的点可区别全染色算法

点可区别全染色(VDTC)是指在满足正常全染色的基础上,还要使得图中由顶点颜色和其关联边颜色构成的顶点色集合也不同,所使用的最少颜色数称为点可区别全色数。提出了一种针对随机图的点可区别全染色算法,算法的基本思想是对图G中的边随机地进行预染色,查找存在边染色不正常的冲突集,然后根据规则逐步迭代,直至使目标函数的值满足要求,此时说明染色成功。实验结果表明,算法能够有效地求得给定点数随机图的点可区别全色数,算法时间复杂度不超过O(n3)。