图的邻点强可区别全色数

图的染色是图论的主要内容之一,它在通讯线路的设计,算法设计与分析以及理论计算机等方面有广泛的应用。如何确定一种图染色法的色数大小,是图染色研究的主要问题。概率方法是一种研究图染色的新方法,它主要用来估计图染色法的色数的上界。利用概率方法研究了图的邻点强可区别的全染色,得到了图的邻点强可区别的全染色的一个上界。     

圈的平方图Smarandachely邻点全色数

对简单图G(V,E)f,是从V(G)∪E(G)到{1,2,Λ,k}的映射,k是自然数,若f满足(1)u,v∈E(G),u≠,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),\C(u)\C(v)\≥1并且|C(v)\C(u)|≥1;则称f是G的Smarandachely邻点全染色.本文给出了圈的平方图的的Smarandachely邻点全色数.     

P_n×P_m图的邻点可区别全染色和邻点强可区别全染色

对Pn×Pm图的邻点可区别全染色和邻点强可区别全染色问题进行了探讨,给出了染色数公式Xat(Pn×Pm)={4 n=m=2 5 n=2 m≥3,ast(pn×pm)=6 n≥3 n≥3{5 n=m=25 n=2 m≥3 6 n≥3 m≥3     

圈的平方图的Smarandachely邻点全色数

对简单图G（V,E）f,是从V（G）∪E（G）到{1,2,A,k}的映射,k是自然数,若,满足（1）u,v∈E（G）,u≠,f（u）≠f（v）;（2）Vuv,uw∈E（G）,v≠w,f（uv）≠f（uw）;（3）uv∈E（G）,＼G（u）＼C（v）＼≥1并且IG（v）＼C（u）1≥1;则称f是G的Smarandachely邻点全染色．本文给出了圈的平方图的的Smarandachely邻点全色数．     

若干直积图的邻点可区别Ⅰ-全色数

应用穷染递推的方法研究了路与扇、路与轮、路与完全图构成的直积图的邻点可区别Ⅰ-全色数,进一步验证了若干直积图的邻点可区别Ⅰ-全染色猜想.     

关于一些图的Double图的全色数

图的全染色是指对顶点和边同时染色,使得相邻或相关联的元素染不同的颜色,其所用最少染色数称为全色数,记为ΧT（G）.本文得到了星、扇和轮的Double图的全色数.     

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

设G1，G1是有限简单图，引入了图G1＊G2的概念，给出了图Pm＊Pn（n≥2，m≥2）的邻点可区别全色数 χα1（Pm＊Pn）={5,当m=n=2时；7,当m=2,n〉2或m〉2,n=2时；9，当m=n=3时；10，当m≥3，n〉3或m〉3，n≥3时。     

路和圈的倍图的邻点可区别全染色

设G(V,E)为简单图,若V(D(G))=V(G)∪V(G'),E(D(G))=E(G)∪E(G')∪｛vivj'｜vi∈(V G),vj'∈V(G')且viυj∈E(G')｝,我们称D(G)为G的倍图,其中G'为G的拷贝。本文讨论了路和圈的倍图的邻点可区别的全染色问题,分别给出了路的倍图D(Pn)的邻点可区别的全色数χat(D(Pn))=4 n=2区别的全色数χat(D(Cn))=6.     

三类特殊图的邻点可区别全染色

图的一个正常的全染色满足相邻顶点的顶点及其关联边的颜色集合不同时,称为邻点可区别全染色,其所用的最少的颜色数称为其邻点可区别全色数。刻画了Cm×Cn图,Fm Fn图;广义Petersen图的邻点可区别全色数。     

路的笛卡尔乘积图的邻点可区别全染色

一个正常的全染色满足相邻顶点的顶点及其关联边所用的色集合不同时,称为邻点可区别全染色,其所用的最少的颜色数称为顶点可区别全色数。刻画了路与路的笛卡尔乘积图的邻点可区别全色数。     

图D_(n,4)的邻点强可区别的全染色

通过分析图Dn,4的结构,利用穷举法和组合分析法讨论了图Dn,4的邻点强可区别的全染色,通过构造具体染色得到了图Dn,4的邻点强可区别的全色数。从而证明了图Dn,4的邻点强可区别的全色数是存在的。     

具有唯一最大度点的Halin图的全色数

本文证明了：对于具有唯一最大度点的Halin图G，有G∈1/T={G|xT（G）=△（G） 1}。这是xT(G)表示图G的全色数，△（G)表示图G的最大度数。     

关于路和路的联图的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的,如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的,如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图P_n■P_n的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.     

关于联图PnVCn的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图PnVCn的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.     

k-方体图的Smarandachely邻点全染色

研究了k-方体图Qk(V,E)的Smarandachely邻点全染色,证明了关于图的Smarandachely邻点全染色猜想于k-方体图成立,r-正则图G(V,E)的Smarandachely邻点全色数sχat(G)=Δ(G)+2,其中sχat(G)表示G(V,E)的Smarandachely邻点全色数。     

关于联图P_n∨C_n的邻点可区别的均匀全染色

一个图G的全染色被称为邻点可区别的如果满足图G中任意两个相邻点所关联的元素所染的色的集合不同.一个图的邻点可区别的全染色被称为均匀的如果满足任意两色所染元素的数目之差的绝对值不超过1.本文研究了联图P_n∨C_n的邻点可区别的均匀全染色并证明它满足邻点可区别的均匀全染色猜想.     

联图CnVKn的全色数

研究了联图CnVKn=2n的全色数，证明了当n〉5时，金色数XT（CnVKn）=2n，从而证明了CnVKn．满足全着色猜想.     

关于路和轮的广义Mycielski图的邻点可区别的边染色

一个图G的边染色被称为邻点可区别的,如果满足图G中任意两个相邻点所关联的边所染颜色的集合不同。研究了图路和轮的广义Mycielski图的邻点可区别的边染色并证明它满足邻点可区别的边染色猜想。     

联图Cn ∨ Kn的全色数

研究了联图Cn∨Kn=2n的全色数,证明了当n≥5时,全色数χT(Cn∨Kn)=2n,从而证明了Cn∨Kn满足全着色猜想.