幂图的全色数

根据幂图的结构性质,利用穷染、替换的方法,研究了幂图Pkn的全色数,并给出了一种染色方案.     

幂图的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

幂图Pkn的邻点可区别全色数和邻点可区别-VE全色数

根据路的幂图Pkn的结构性质,用穷染、递推的方法,讨论了Pkn的邻点可区别全染色和邻点可区别-VE全染色,得到了相应的色数,并给出了一种染色方案.     

低度外平面图的点强全染色

图G的一个k-点强全染色是指图G的正常全染色f，若任意x，y∈N[υ]，有f(x)≠f(y)，简记为k-VSTC，称xT^υ5(G)=min｛k／G有k-VSTC}为G的点强全色数。研究了低度外平面图的点强全染色，证明了对△(G)=3的外平面图G有4≤xT^υs(G)≤5。     

图CmVWn的点可区别全色数

对于圈和轮的联图,给出了一种点可区别的全染色方法,并得到了其点可区别的全色数.     

六角系统的点强全色数

对图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的最大度和点强全色数．     

三角剖分图的点面全色数

平面图G(V,E,F)的点面全色数X_e(G)是使得集合V(G)∪F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文证明了:若G是三角剖分图,则4≤X_e(G)≤6。     

图Cm∨Wn的点可区别全色数

对于圈和轮的联图，给出了一种点可区别的全染色方法，并得到了其点可区别的全色数．     

SmVPn的邻点可区别全色数

设G的阶数不小于2的简单连通图。G的k-正常全染色称为是邻点可区别的，如果对G的任意相邻的两顶点，其点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为G的邻点可区别全色数。本文主要是给出了星图和路的联图的邻点可区别全色数，并提出了一猜想。     

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

讨论并得到了路、圈、完全图、星、扇、轮的Mycielski图的点可区别全色数.     

两类冠图的点边邻点可区别全染色

 图的染色理论是图论的一个重要研究领域,求解图的色数被认为是一个NP-hard问题。对简单连通图G(V,E),存在一个正整数k,使得映射f :V(G)∪ E(G)→{1,2,…,K},如果对∀uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的点边邻点可区别全染色(又称为邻点可区别VE-全染色),而χ_at^ve (G)=min{k|k－VE－AVDTC},称为G的点边邻点可区别边色数(又称为邻点可区别VE-全色数),其中色集合C(u)={f(u)}∪{f(uv)|uv∈E(G)}。本文构造了两类冠图C_m·S_n和C_m·P_n,研究了两类冠图C_m·S_n和C_m·P_n的点边邻点可区别全染色。根据C_m·S_n和C_m·P_n的结构性质,用穷染递推的方法,得到了它们的相应色数,给出一种染色方案。     

△(G)≥6的Halin图的点强全染色

图G(V，E)的正常k-全染色σ称为G(V，E)的k-点强全染色当且仅当A↓v∈V(G)，N[v]的元素染不同色，其中N[v]={uluv∈EG)}∪{v}，xT^vs(G)=min{k|存在G的k-点强全染色}称为G(V，E)的点强全色数。本文证明了：对于△(G)≥6的Halin图G(V，E)，有xT^vs(G)≤△(G) 2，其△(G)表示图G的最大度。     

圈与星的联图的邻点可区别全色数

对于一个正常的全染色，相邻点满足顶点及其关联边染色色集不同的条件时，称为邻点可区别全染色。其所用最少染色数称为邻点可区别全色数。就圈Cm与星Sn的联图CmVS,得到m，n任意取值下的邻点可区别全色数。     

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

P_m∨W_n的点可区别全色数

根据点可区别全染色的概念及其染色方法,讨论了路与轮联图的点可区别全染色,给出了路与轮联图的点可区别全色数的结论及其证明,为进一步探讨其他联图的点可区别全染色提供了理论证据,丰富了图的点可区别全染色的结果.     

几类冠图的邻强边色数

图的强染色来自计算机科学,有着很强的实际背景,但确定图的强色数是非常困难的。张忠辅,刘林忠,王建方等研究了图的邻强边染色,并提出了邻强边染色猜想：对任意连通图GG,{y}≥3且G≠C5有△≤X’ax（G）≤△＋2。研究了树、圈、扇、轮、完全二部图及完全图的冠图的邻强边色数;证明了：△≤X’as（G）≤△＋1,且X’as（G）≤△＋1当且仅当G[V△]≠Ф。     

点不交的m个C3]的并的点可区别全染色

利用μ(G)的定义确定了点不交的m个C₃(m≥2)的并的点可区别全色数的下界, 并借助矩阵给出了点不交的m个C₃(m≥2)的并的点可区别全染色方法, 进而确定了它的点可区别全色数.