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

图G的邻点可区别V-全染色就是相邻的边、顶点与其关联边必须染不同的颜色,同时要求相邻顶点的色集合也不相同,所用的最少颜色数称为图G的邻点可区别V-全色数.根据邻点可区别V-全染色的约束规则,设计了一种启发式的邻点可区别V-全染色算法.该算法借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功.给出了算法的详细描述以及算法分析和算法测试结果.实验结果表明,该算法有很好的执行效率,并可以得到随机图的邻点可区别V-全色数,验证了邻点可区别V-全染色猜想,并且算法的时间复杂度不超过O(n3).     

关于图rK2∨K8的邻点可区别全色数

对一个简单图G的一个正常全染色，来说，G的点v的色集合C（v）是与v关联的边的颜色以及点v的颜色所构成的集合．对此f，如果G的任意两个相邻顶点的色集合不同，则称，为G的邻点可区别全染色．对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数．对图rK2∨K8的邻点可区别全色数进行了讨论．     

关于图rK2 ∨ Ks的邻点可区别全色数

对一个简单图G的一个正常全染色f来说,G的点v的色集合C(V)是与v关联的边的颜色以及点v的颜色所构成的集合.对此f,如果G的任意两个相邻顶点的色集合不同,则称f为G的邻点可区别全染色.对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数.对图rK2∨K8的邻点可区别全色数进行了讨论.     

两类运算图的Smarandachely邻点可区别全染色

一个图G的正常全染色满足相邻点的色集合互不包含时称为Smarandachely邻点可区别全染色,其所用的最少色数称为Smarandachely邻点可区别全色数。给出了倍图的Smarandachely邻点可区别全色数的上界及一些图的Mycielski图的Smarandachely邻点可区别全色数。     

关于一类图的邻点可区别全染色

图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点及其关联边的颜色集合不同;对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为χat(G);给出了一类特殊图类的邻点可区别全色数.     

K4-minor-free图的邻点可区别全染色

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同.论文确定了k4-minor-free图的邻点可区别全色数.     

两类3-正则图的邻点可区别I-全染色

图G的I-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个I-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别I-全染色所用的最少颜色的数目称为图G的邻点可区别I-全色数.本文给出了两类3-正则图的邻点可区别I-全色数.     

P_m∨F_n及P_m∨W_n的邻点可区别I-全染色

图G的I-全染色是指对图G的顶点和边染色,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.图G的一个I-全染色称为是邻点可区别的,如果任意两个相邻顶点u,v的色集合C(u)≠C(v),这里C(u)={f(u)}∪{f(uv)|uv∈E(G)}.而图G的邻点可区别I-全染色中所用的最少色数称为图G的邻点可区别I-全色数.讨论路与扇的联图Pm∨Fn、路与轮联图Pm∨Wn的邻点可区别I-全染色问题,根据这类图的结构性质运用色构造法给出它们的邻点可区别I-全染色方法,从而有效地确定其邻点可区别I-全色数.     

若干图的倍图的邻点可区别边(全)染色

设G是具有顶点集V(G)和边集E(G)的简单图。如果G的一正常边染色σ满足对任意uv∈E(G),有Cσ(u)≠Cσ(v),其中Cσ(u)为点u的关联边所染颜色构成的集合,则称σ为G的邻点可区别边染色。如果G的一正常全染色σ满足对任意uv∈E(G),有Sσ(u)≠Sσ(v),其中Sσ(u)表示点u及u的关联边所染颜色构成的集合,则称σ为G的邻点可区别全染色。图G的邻点可区别边(或全)染色所需的最少的颜色数,称为G的邻点可区别边(或全)色数,并记为χ’as(G)(或χat(G))。给出了图G的倍图D(G)的以上两个参数的上界,并对完全图与树,确定了它们的倍图的邻点可区别边色数与全色数的精确值。     

完全图的广义Mycielski图的邻点可区别的全色数

对图G的一个k-正常全染色法,若满足相邻点的点染色和关联边的色集合不同时,称该染色法为邻点可区别全染色,其所用小染色数k称为G的邻点可区别全色数.得到了完全图Km的广义Mycieski图Mn(Km)(n≥1,m≥3)的邻点可区别全色数.     

图K15-E(K3)和K17-E(K3)的邻点可区别全染色

利用组合分析法和构造染色的方法, 讨论 图K_15-E(K₃)和K₁₇-E(K₃)的邻点可区别全染色, 确定了它们的邻点可区别全色数分别为16和19.     

两类4-正则循环图的邻点可区别全色数

设G是阶数不小于2的连通图,则其邻点可区别全染色是指G中任意两个相邻的顶点有不同的颜色和色集合,且任意相邻的两条边及一个顶点与其关联边的颜色也不相同．给出了两类邻接矩阵的第一行分别为（0,1,0,1,0,…,0）和（0,1,0,0,1,0,…,0）的循环图的邻点可区别金色数．     

关于几类特殊图的Mycielski图的邻点可区别全色数

设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.     

关于图K2n+1-E(2 K2)的邻点可区别全色数

用K2n 1-E(2K2)表示2n 1阶的完全图删掉两条不相邻的边所得到的图,给出了图K2n 1-E(2K2)的邻点可区别全色数.     

关于△（G）=5的2-连通外平面图的邻点可区别全色数

给出了△（G）=5的2-连通外平面图的邻点可区别全色数．     

关于Δ(G)=5的2-连通外平面图的邻点可区别全色数

给出了Δ(G)=5的2-连通外平面图的邻点可区别全色数.     

联图 Ws∨Km,n的邻点可区别全色数

图的邻点可区别全染色(AVDTC)数为χ_at(G)，有猜想：x_at(G)≤Δ(G)+3. 联图 W_s∨K_{m,n的邻点可区别全色数被确定为χat(Ws∨Km,n)=Δ( Ws∨Km,n)+1或Δ(Ws∨Km,n)+2.}     

Cm×Kn的邻点可区别全染色

设G（V，E）是阶数至少为2的简单连通图，k是正整数，V∪E到{1，2，3，…，k）的映射f满足：对任意uυ，υw∈E（G），u≠w，有f（uv）≠f（υw）；对任意uυ∈E（G），有，（u）≠，（υ），f（u）≠f（uυ），f（υ）≠f（uυ）；那么称f为G的k-正常全染色，若，还满足对任意uυ∈E（G），有C（u）≠C（υ），其中C（u）={（u））∪{f（uυ）｜uυ∈E（G），υ∈V（G）），那么称，为G的k-邻点可区别的全染色（简记为k-AVDTC），称min{k｜G有k-邻点可区别的全染色）为G的邻点可区别的全色数，记作xat（G）．本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数．     

C_m×K_n的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…,k}的映射f满足:对任意uv,vw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)},那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G).本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数.