k-方图的邻点可区别无圈边染色

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.图G的邻点可区别无圈边色数记为χ′_^(aa)(G),即图G的一个邻点可区别无圈边染色所用的最少颜色数.通过构造具体染色的方法,给出了一些k-方图的邻点可区别无圈边色数.     

图的一般邻点可区别均匀边染色和一般邻点可区别均匀全染色

提出了 一般邻点可区别均匀边染色,一般邻点可区别均匀全染色的新概念,具体研究了路、圈、星、扇、轮、完全二部图、2维平面网格图Pm×Pn的一般邻点可区别均匀边染色和全染色,并给出这些图的一般邻点可区别均匀边染色指标和全染色指标.     

没有K4-图子式的图的邻点可区别全染色

图 $G$ 的邻点可区别全染色是$G$ 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. $G$的邻点可区别全色数$\chi''''_{a}(G)$是使得$G$有一个$k$-\!邻点可区别全染色的最小的整数$k$. 本文完整刻画了没有$K_4$-\!图子式的图的邻点可区别全色数. 证明了：如果 $G$是一个满足最大度$\Delta \ge 3$且没有$K_4$-\!图子式的图, 则$\Delta+1\le \chi''''_{a}(G)\le \Delta+2$, 且$\chi''''_{a}(G)=\Delta+2$当且仅当$G$中含有两个相邻最大度点.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.     

图的邻点可区别无圈边染色的一个界

图G的一个正常边染色被称作邻点可区别无圈边染色,如果G中无二色圈,且相邻点关联边的色集合不同.应用概率的方法得到了图G的一个邻点可区别无圈边色数的上界,其中图G为无孤立边的图.     

关于图的一般邻点可区别边染色

给出了轮图W_n、扇图F_n、风车图K_2~t、图D_(m,4)、图D_(m,n)、齿轮图W_n的一般邻点可区别色指标.     

图K_3~cVK_t的点可区别正常边染色

图G的正常边染色称为是点可区别的,如果对G的任意两顶点的关联边的颜色构成的集合不同.对图G进行点可区别正常边染色所需要的最少颜色数称为图G的点可区别正常边色数,记为x_s'(G).给出了3阶空图与t阶完全图的联图的点可区别正常边色数.     

图的一般邻点可区别均匀边染色和均匀全染色

提出了一般邻点可区别均匀边染色和全染色的新概念,研究了路P_n、圈C_n、星S_n、扇F_n、轮W_n、完全二部图K_(m,n)、2维平面网格图P_m×P_n的一般邻点可区别均匀边染色和全染色,具体给出这些图的一般邻点可区别均匀边染色和全染色指标.     

无K_4-图子式的图的谱半径(英文)

Ｇ是一个无Ｋ４－图子式、顶点数为ｎ的简单图,ｐ（Ｇ）是图Ｇ的谱半径．本文得出一个关于ｐ（Ｇ）的上确界：等式成立当且仅当 Ｇ ≌Ｋ２　（ｎ－２）Ｋ１,其中 Ｇ１　Ｇ２是由 Ｇ１∪Ｇ２组成、并且Ｇ１中的第一个点和Ｇ２中的每一个点之间都有一条边相连：（ｎ－２）Ｋ１表示（ｎ－２）个孤立点的集合．     

图K_(3,4)∨K_t的点可区别正常边染色

设f是图G的一个正常边染色.对任意x∈V(G),令S(x)表示与点x相关联的边的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有S(u)≠S(v),则称f是图G的一个点可区别正常边染色.对一个图G进行点可区别正常边染色所需的最少的颜色的数目称为G的点可区别正常边色数,记为χ_s'(G).讨论了图K_(3,4)∨K_t的点可区别正常边染色及其色数,利用正多边形的对称性构造染色以及组合分析的方法,确定了图K_(3,4)∨K_t的点可区别正常边色数,得到了当t是大于等于2的偶数以及t是奇数且3≤t≤25时,χ_s'(K_(3,4)∨K_t)=t+7;当t是奇数且t≥27时,χ_s'(K_(3,4)∨K_t)=t+8.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,…,k}的G的一个正常边染色.用w_σ（x）表示顶点x关联边的颜色之和,即w_σ（x）=∑_e∋x σ（e）,并称w_σ（x）关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为χ'_∑（G）.现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,...,k}的G的一个正常边染色.用w_σ(χ)表示顶点χ关联边的颜色之和,即■,并称w_σ(x)为x关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为x′_Σ(G).现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

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

提出了图的邻点可区别全染色的概念, 给出了圈、完全图、完全二部图、扇、轮和树的邻点可区别全色数.     

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

设f:V(G)∪E(G)→{1,2,…,k}是图G的一个正常k-全染色。令■其中N(x)={y∈V(G)|xy∈E(G)}。对任意的边uv∈E(C),若有Φ(u)≠Φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色。图G的邻点全和可区别全染色中最小的颜色数k叫做G的邻点全和可区别全色数,记为f tndi∑(G)。本文确定了路、圈、星、轮、完全二部图、完全图以及树的邻点全和可区别全色数,同时猜想:简单图G(≠K2)的邻点全和可区别全色数不超过△(G)+2。     

Pn∨Pm的邻点可区别边染色

对于图的邻点可区别染色,给出了路的联图PnPm的邻点可构别边色数.     

广义θ-图的邻点可区别的全染色

u,v两点间连多于三条内部不相交的路且至多有一条长度为1的图,称为广义θ-图.本文给出了广义θ-图的邻点可区别的全染色.     

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

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

若干倍图的邻点可区别Ⅵ-全染色

图的一个边正常的全染色满足相邻点的色集合不同时被称为邻点可区别Ⅵ-全染色,把所用的最少颜色数称为邻点可区别Ⅵ-全色数,其中任意一点的色集合为点上与关联边所染的颜色构成的集合.应用构造邻点可区别Ⅵ-全染色函数法得到了路、圈、星和扇的倍图的邻点可区别Ⅵ-全色数,进一步验证图的邻点可区别Ⅵ-全染色猜想.     

若干倍图的邻点可区别Ⅰ-全染色

通过构造邻点可区别Ⅰ-全染色函数得到了路、圈、星、扇和轮的倍图的邻点可区别Ⅰ-全色数,验证了它们满足邻点可区别Ⅰ-全染色猜想.     

图的半强积的邻点可区别染色

两个简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图,其中两个顶点(u,v)与(u',v')相邻当且仅当u=u'且vv'∈E(H),或uu'∈E(G)且vv'∈E(H).图的邻点可区别边(全)染色是指相邻点具有不同色集的正常边(全)染色.统称图的邻点可区别边染色与邻点可区别全染色为图的邻点可区别染色.图G的邻点可区别染色所需的最少的颜色数称为邻点可区别染色数,并记为X_a~((r))(G),其中r=1,2,且X_a~((1))(G)与X_a~((2))(G)分别表示G的邻点可区别的边色数与全色数.给出了两个简单图的半强积的邻点可区别染色数的一个上界,并证明了该上界是可达的.然后,讨论了两个树的不同半强积具有相同邻点可区别染色数的充分必要条件.另外,确定了一类图与完全图的半强积的邻点可区别染色数的精确值.