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∨F_n的邻点可区别全染色

对一个正常的全染色满足相邻点的点及其关联边染色的色集不同时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别全色数.就圈Cm与扇Fn的联图Cm∨Fn,得到了在m,n不同取值情况下的邻点可区别全色数.     

冠图Cm·Fn、Cm·Sn与Cm·Wn的邻点可区别Ⅰ-全染色

图G的Ⅰ-全染色是指若干种颜色对图G的顶点和边的一个分配,使得任意两个相邻的点的颜色不同,任意两条相邻的边的颜色不同.在图G的一个Ⅰ-全染色下,G的任意一个点的色集合是指该点的颜色以及与该点相关联的全体边的颜色构成的集合.图G的一个Ⅰ-全染色称为是邻点可区别的,如果任意两个相邻点的色集合不相等.对一个图G进行邻点可区别...     

平面图的邻点可区别全染色

图G的一个正常全染色f称为是邻点可区别的,如果G中任何相邻点的点及其关联边的颜色集合不同.对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数,记为xat(G).证明了xat(G)≤△(G)+2对任意的△(G)≥11且围长至少为4的平面图G成立.     

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

图的邻点可区别全染色是最近提出的新概念.本文给出了风车图Kt3、齿轮图Wn和图Dm,4以及Dm,n和Fm,n的邻点可区别全色数.     

若干广义Petersen图的邻点可区别全染色

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。     

图的邻点可区别全染色算法

在图 G 的一个正常全染色下,G 中任意一点 v 的色集合是指点 v 的色以及与 v 关联的全体边的色所构成的集合。图 G 的邻点可区别全染色就是图 G 的正常全染色且使相邻点的色集合不同,其所用最少颜色数称为图 G的邻点可区别全色数。设计了一种启发式的邻点可区别全染色算法,该算法根据邻点可区别全染色的约束规则,确定四个子目标函数和一个总目标函数,然后借助染色矩阵及色补集合逐步迭代交换,每次迭代交换后判断目标函数值,当目标函数值满足要求时染色成功。实验结果表明,该算法可以得到图的邻点可区别全色数,并且算法的时间复杂度不超过 O（n3）。     

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

给出了圈的阶数至少为4的单圈图的邻点可区别全色数.如果E(G[VΔ])=,则χat(G)=Δ(G) 1,否则,χat(G)=Δ(G) 2,其中Δ(G)表示图G的最大度.     

关于邻点可区别全染色的几个新结果

邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同.顶点ν的色集是ν的颜色及其与ν关联的所有边的颜色.我们给出了几类特殊图的邻点可区别全色数.     

立方图的邻点可区别全染色及一般邻点可区别全染色

根据圈的立方图的性质,利用穷染、置换的方法,研究了立方图C3n的邻点可区别全染色及一般邻点可区别全染色.通过设计染色方案,给出了立方图C3n的邻点可区别全色数及一般邻点可区别全色数指标,且色数均可取到下界.     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

直积图的邻点可区别全染色

设G,H为简单图.给出直积图G×H的邻点可区别全色数的一个上界,得到星、轮、扇分别与m阶路、圈的直积图的邻点可区别全色数.     

关于Cm·Cn,Cm·Sn和Cm·Kn的邻点可区别全色数

一个图的正常全染色如果相邻点的点染色及其关联边染色集合是不同的,则称为图的邻点可区别全染色,其所用到的最少颜色数称为图的邻点可区别全色数.该文得到了冠图圈与圈(星,完全图)的邻点可区别全色数.     

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

G(V,E)是一个简单图,k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射.如果uv∈E(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.称 f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到路和圈的联图的邻点可区别E-全色数.     

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

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

联图WmVCn的邻点可区别全染色

邻点可区别全染色是在全染色的基础上,要求相邻顶点的色集合互不相同．通过设计染色方案,给出轮与圈的联图WmVCn的邻点可区别全色数．     

蛛网图的邻点可区别V-全染色

研究了蛛网图的邻点可区别V-全染色.根据蛛网图的结构特点,利用穷染的方法,得到了蛛网图的邻点可区别V-全色数.进一步验证了图的邻点可区别V-全染色猜想.     

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk（G）（其中k为正整数）的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.     

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邻点可区别的全色数.     

低度系列平行图的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意两个相邻顶点,它们的顶点及关联边的颜色构成的集合不同.满足上述条件的最小k称为是G的邻点可区别全色数.文中从系列平行图的结构性质出发,利用换色技巧、归纳法以及组合方法对最大度不大于7的系列平行图的邻点可区别全染色进行了研究.得到了当低度系列平行图中不含相邻最大度点时,其邻点可区别全色数是最大度加1,否则,其邻点可区别全色数的上界为最大度加3.