若干图的集合点染色

图G的集合点染色是集合X中的非空子集在点集V(G)上的一个分配,满足相邻点的色集合不相同、相邻点上色集合交不为空集,且每个点上的色集合长度不低于该点的度.此时把X中包含颜色的最小数目称为图G的集合点色数.应用构造染色函数法和色集合分配法研究圈、路、轮、扇、星以及路与路的联图,得到确切的集合点色数,进一步推出圈与圈的联图、路与圈的联图的集合点色数.     

若干图广义Mycielski图的点边邻点可区别的全染色

对简单图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的点边邻点可区别全染色,且称最小的数k为图G的点边邻点可区别全色数.本文讨论了星,扇,轮,圈等图的广义Mycielski图的点边邻点可区别全染色,得到了它们的点边邻点可区别全色数,其中每个点的色集合包含该点及其关联边的颜色.     

图Cm∨Cn的Smarandachely邻点可区别全色数

图的一个正常全染色满足相邻点的色集合互不包含时被称为Smarandachely邻点可区别全染色.使图G存在使用了k种色的Smarandachely邻点可区别全染色的最小数k称为图G的Smarandachely邻点可区别全色数,其中任意一点的色集合为该点所染色与其关联边所染色的并.文章给出了当(m相似文献   

广义Mycielski图的邻点可约边染色

对简单图G(V,E),若存在自然数k(1≤k≤△(G))和映射f:E(G)→{1,2,…,k}使得对任意相邻两点u,(υ)V(G),u(υ)E( G),当d(u)=d(υ)时,有C(u)=C(υ),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数.     

单圈图的邻强边染色

设G是阶数不小于3的简单连通图,G的k-正常边染色称为是邻强的,如果G的任意相邻的两顶点的关联边的颜色构成的集合不同.对一个图G进行邻强边染色所需要的最少的颜色数称为是G的邻强边色数.本文研究了单圈图的邻强边染色.     

关于Cm(。)Cn和Cm(。)Pn星全色数

对于一个图G=G(V(G),E(G)),用V(G)和E(G)表示图的顶点集合和边集合.图G的3个顶点的路边和顶点着有5种色,跑遍图G的所有k星全着色所取得的最小数k称为图G的星全色数,简记为χst(G).主要研究了Cm(。)Cn和Cm(。)Pn2种冠图的星全染色规律,并得出它们的星全色数.     

联图PmVSn,n的邻点可区别全染色

简单连通图G(V,E)的κ-正常全染色f称为邻点可区别的,如果对G(V,E)的任意相邻两顶点,其顶点的颜色及关联边的颜色构成的集合不同.这样的κ中最小者称为G(V,E)的邻点可区别全色数.研究了路与双星图的联图PmV Sn,n邻点可区别的全染色问题,得到了联图PmV Sn,n邻点可区别的全色数.     

扇和轮的倍图的点可区别均匀边染色

对于简单图G的正常边染色f,若对于u,v∈V(G),有C(u)≠C(v),称f是图G的点可区别边染色,(其中C(u)={f(uv)|uv∈E(G)}).若满足|Ei|-|Ej|≤1(i,j=1,2,…,k),(其中e∈Ei,f(e)=i(i=1,2,...,k)),则称f是图G的点可区别均匀边染色.本文讨论了扇和轮的倍图的点可区别均匀边染色.     

关于图的反符号边控制

引入了图的反符号边控制的概念,设G=(V,E)是一个图,一个函数f:e→{-1, 1}如果对任意e∈E(G),均有∑e′∈N[e]f(e′)≤0,则称f为图G的一个反符号边控制函数.图G的反符号边控制数定义为-γs(G)=max{∑e∈Ef(e)|f为图G的反符号边控制函数}.在本文中,我们主要给出了图的反符号边控制数的两个上界,并确定了几类特殊图的反符号控制函数.     

关于Cm o Cn和Cm o Pn星全色数

对于一个图G=G（V（G）,E（G））,用V（G）和E（G）表示图的顶点集合和边集合.图G的3个顶点的路边和顶点着有5种色,跑遍图G的所有k星全着色所取得的最小数k称为图G的星全色数,简记为sχt（G）.主要研究了Cm o Cn和Cm o Pn2种冠图的星全染色规律,并得出它们的星全色数.     

关于Cm×C5n的全色数和邻强边色数

设G是一个简单图,k为正整数,V(G)∪E(G)到{1,2,…,k}的一个映射f满足:对于任意的uv∈E(G)有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);任意的uv,vw∈E(G),u≠w,有f(uv)≠f(uw),则称f为G的k-全染色,简记为k-TC,并称XT(G)=min{k|G存在k-TC}为G的全色数.证明了圈Cm与圈C5n的笛卡尔积图的全色数和邻强边色数都为5.     

偶阶完全图的邻强边染色法注

对于| V(G)|≥3的连通图G(G,E),若k-正常边染色法满足相邻点的边染色集合不相同,则称该染色法为k-邻强边染色,其最小的k称为G的邻强边色数.本文重新给出了Kp(p≥4且p≡0(mod 2))的邻强边染色法.     

关于Pn∨Kn,n的邻强边染色

对图G的k正常边染色使得相邻点的关联边色集合不同时,称为邻强边染色法,运用最小的k称为G的邻强边色数.得到了Pn∨Kn,n的邻强边色数.     

关于图的两类边控制数

引入了图的反符号边全控制的概念．设G=（V,E）是一个图,N（e）表示G中与e相邻的边集,函数f：E→{＋1,-1},如果对任意e∈E（G）均有∑f（e’）≤0,其中e’∈N（e）,则称,为图G的一个反符号边全控制函数．而γ’st（G）=max{∑f（e）｜f为G的反符号边全控制函数,e∈E（G）称为图G的反符号边全控制数．分别给出了图的反符号边全控制数和^符号边控制数的一个界限,并确定了轮图的反符号边全控制数和完全偶图Km,n的珏符号边控制数的下界．     

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

若图G的一个k全染色?满足:任意相邻两点u和v[uv∈E(G)]的色集合C_?(u)、C_?(v)中的所有元素之和互不相同,则称G存在一个k-邻和可区别全染色.k的最小值称为图G的邻和可区别全色数.研究了两类冠图C_m。P_n和C_m。C_n的邻和可区别全染色方法,得到了它们的邻和可区别全色数.     

伪-Halin图的邻强边染色

对图G(V，E)，一正常k-边染色f称为图G(V，E)的k-邻强边染色，当且仅当任意uv∈E(G)，有f[u]≠f[u]，其中f[u]={f(uw)|uw∈E(G)}，并称x′。(G)=min{k|存在G的一k-ASEC}为G的邻强边色数．研究了△(G)≥5的伪-Halin图的邻强边色数，并通过归纳法证明了对△(G)=5的伪-Halin图G，有5≤x′as(G)≤6．如果E(G[V△])≠Ф，则,x′as(G)=6．并提出猜想：对|V(G)|≥6的连通图G(V，E)有△(G)≤x′as(G)≤△(G) 2．其中△(G)为G的最大度．     

关于Cm×Kn的邻点可区别全色数

一个图的正常全染色如果相邻点的点染色及其关联边染色集合是不同的,则称为图的邻点可区别全染色;其所用到的最少颜色数称为图的邻点可区别全色数.得到了圈与完全图的笛卡尔积图的邻点可区别全色数.     

关于图的局部着色

G.Chartand[1]引入了一个图G的局部色数x1(G)的概念,在本文中的我们主要出了图的局部色数的界限,证明了对任意n阶图G(n≥2),均有x1(G) x1(■)≤2n-1,并确下了一些特殊图的局部色数.     

三色拉姆塞数R_3（C_8）研究

用r种颜色对图G的所有边着色,记着第i色的边构成的子图为Gi,如果存在一种着色方法使得每一个Gi（1≤i≤r）都不包含图H,则称图G对于H可以r着色.拉姆塞数Rr（H）是使得完全图Kn对于H不可以r着色的最小正整数n.令Cm表示长度为m的圈,Dzido等证明了R3（C2k）≥4k.本文对k=4的情形进行研究,利用计算机,通过大量的计算证明了R3（C8）=16.     

图的反符号星k控制数

设G=(V,E)是一个图,一个函数f:E→-1,+1如果∑f(e)≤0 e∈E[v]对于至少k个顶点v∈V(G)成立,则称f为图G的一个反符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的反符号星k控制数定义为γrkss(G)=max{∑f(e) e∈E│f为图G的反符号星k控制数}。得到了一般图的反符号星k控制数的若干上界,对文[6]中的结果进行了推广,还确定了路Pn和圈Cn的反符号星k控制数。