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

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

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

冠图C_n■C_m的邻点可区别均匀E-全染色

讨论了冠图C_n■C_m的邻点可区别均匀E-全染色,并得到了它们的邻点可区别均匀E-全色数.对简单图G,如果图G存在一个染色法f,使得任意两个相邻的顶点染不同的颜色;任意一条边与其关联的点染不同的颜色;任意两个相邻的点的色集合不相同,并且任意两色所染元素的数目之差不超过1,则称该染色法为G的邻点可区别均匀E-全染色,其所用最少颜色数称为该图的邻点可区别均匀E-全色数.     

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

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

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

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

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

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设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的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

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

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

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

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

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

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

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

研究了冠图SnPm,PnSm,SnCm和CnSm的邻点可区别I-全染色问题.根据这些冠图的结构特征,构造了一个从集合V(G)∪E(G)到色集合{1,2,…,k}的函数,给出了一种染色方案,得到了它们的邻点可区别的I-全色数.     

几类笛卡尔积图的邻点可区别全染色

图G的邻点可区别全染色是指G的任意相邻顶点具有不同色集的全染色,所需要的最少颜色数称为G的邻点可区别全色数.文章得到了圈与星、轮、扇的笛卡尔积图的邻点可区别全色数.     

一些联图的邻点可区别一边全染色

讨论了C_m+C_n,S_m+S_n,F_m+F_n,W_m+W_n等一些联图的邻点可区别一边全染色,得到了它们的邻点可区别一边全色数.     

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

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

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

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

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

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

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

几类有趣图的邻点可区别全染色

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

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

研究若干联图的邻点可区别全染色,证明了:当n≥3时,χat(Kn∨Cn)=χat(Kn∨Pn)=2n+1;当n≥4时,χat(Kn∨Wn?1)=χat(Kn∨Fn?1)=χat(Kn∨Sn?1)=2n+1.     

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

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

一类沿联图的邻点可区别全染色

为了解决图的邻点可区别全染色中一个图的色数算法问题,从沿联图的结构特点出发,对一类沿联图的邻点可区别全染色问题进行了研究,并得到了它的邻点可区别全色数.