关于几类图的邻点可区别关联色数

邻点可区别关联着色的定义是在关联着色的基础上提出的,是使得相邻顶点的颜色集不同的关联着色。主要研究了几类特殊图的邻点可区别关联色数,包括风车图、齿轮图及在此基础上扩充的图Dm、n,拓展了图着色的领域,便于更好地研究图的结构。     

Cm

得到了联图Cm     

点可区别全色数的一个界

图G的一个正常全染色被称作点可区别全染色,如果G中任意两个点的色集合不同,其中每个点的色集合包含该点及其关联边的颜色。在点可区别全色数界(χvt(G)≤|V(G)|+2)的基础上,应用概率的方法得到了阶数为n,且无孤立边的简单图G的点可区别全色数的一个较小上界。     

图P_m V W_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数．得到了路与轮的联图的点可区别边色数．     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

六角系统的点强全色数

对图G及正整数k,映射σ：VUE→{1,2,…,k}满足：（1）任意e1,e2∈VUE,如果e1,e2是相邻或相关联的,则有σ（e1）≠σ（e2）;（2）对u,v,w∈V（G）,uw,vw∈E（G）,uv￠E（G）有σ（u）≠σ（v）,则称σ为G的一个k-点强全染色,并且xτ^vs（G）={k｜存在G的k点强全染色},称为G的点强全色数．研究了六色系统图G的点强全色数,得到△（G）＋l≤xτ^vs;（G）≤△（G）＋2,其中△（G）,xτ^vs（G）分别表示G的最大度和点强全色数．     

皇冠图Gn,m的邻点可区别关联色数

图的邻点可区别关联色数的确定比其关联色数的确定更加困难.通过研究皇冠图的结构,运用着色技巧, 完全确定了皇冠图的邻点可区别关联色数.     

n-方体的点可区别全色数的渐近性态

令Qn为n-方体,图G的点可区别全色数为χvt(G),那么limn→∞vχt(Qn)n=1 q*.这里q*=0.293815…是方程(x 1)x 1=2xx的唯一的正根.     

联图的邻点可区别无圈边染色

根据图的邻点可区别无圈边染色的定义,利用构造的方法讨论联图Pm∨Wn、Pm∨Fn、Pm∨Pn、Pm∨Sn和Cm,n的邻点可区别无圈边染色,并给出它们的邻点可区别无圈边色数及其证明,且均满足图的邻点可区别无圈边染色猜想.     

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

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

循环图Cn〈1，n/2〉的关联色数

循环图具有很强的对称性,作为有价值的通讯网络拓扑已受到广泛的关注．对三度循环图Gn〈1,n/2〉进行了研究,完全确定了其关联色数．     

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

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

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

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

若干Hamming距离图的邻点可区别全染色

一个正常的全染色满足相邻点的点染色及关联边的色集不同时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别的全色数。文中研究了一些Hamming距离图的邻点可区别全染色。     

联图的星色数

为了进一步研究图的星色数,根据与路有关的联图结构的特殊性,运用结构图论的方法分别证明了路与路、路与圈、路与星图及路与扇的联图的星色数,同时,给出了一种简单易行的星染色方法。     

图半群的边色数

引入图半群Fv／ρε的边色数x’（Fv／ρε）的概念，并证明了若Fv／ρε单图半群，则x’（Fv／ρε）=△或x’（Fv／ρε）=△＋1，这里△为图半群Fv／ρε的最大度．     

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

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

计算圆色数的混合整数规划方法

通过讨论圆色数几个等价的定义,建立了一个求解圆色数χc(G)近似值的混合整数规划,并进一步给出了圆色数χc(G)的精确值．之后,利用这些结果计算了一类特殊图的圆色数χc(G),确定了此类图的圆色数的精确值．