关于Sm∨Kn,n的全色数

图染色是实际问题的重要数学模型,也是图论的研究内容之一.文章通过一类联图的全色数的确定,得到了阶星Sm和完全等二部图Kn.n联图的全色数.     

关于S_m∨K_(n,n)的全色数

图染色是实际问题的重要数学模型,也是图论的研究内容之一.文章通过一类联图的全色数的确定,得到了阶星Sm和完全等二部图Kn,n联图的全色数.     

星和完全等二部图联图的邻强边染色

对于1V（G）≥31的连通图G（V,E）,若缸正常边染色法满足相邻的边染色集合不同,则称该染色法为缸邻强边染色法,其最小的称为G的邻强边色数。本文用特殊的方法记图的染色,并得到了星和完全等二部图联图的邻强边色数。     

图Pn∨Km,n的均匀全色数

对于图G(V,E)的正常k-全染色f称为G(V,E)的k-均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.eχt(G)=min{k|G有k-均匀全染色}称为G的均匀全色数.利用均匀边染色的相关结论,探讨了路Pn与完全二部图Km,n的联图Pn∨Km,n的均匀全色数.     

图Pn V km,n的均匀全色数

对于图G（V，E）的正常七一全染色／称为G（V，E）的七一均匀全染色，当且仅当任意2个色类中的元素总数至多相差1．Xet（G）=min{k｜G有七一均匀全染色｜称为G的均匀全色数．利用均匀边染色的相关结论，探讨了路Pn与完全二部图km,n的联图PnVm,n的均匀全色数．     

完全多部图满足全色数猜想的一种新的证明方法

Ｂｅｈｚａｄ〔１〕和Ｖｉｚｉｎｇ〔２〕独立提出了全色数精想：对任意图Ｇ，有ｘＴ（Ｇ）≤Δ（Ｇ）＋２。本文的主要结果如下：（１）用一种新的方法证明了完全多部图满足全色猜想（２）证明了点数不大于１０的图满足全色数猜想。     

关于联图的均匀全色数

对一个正常的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数。本研究得到了G∨H的均匀全色数为它的阶,若满足以下条件之一:(1)当G的最大度等于它的阶减1,且G∨H的顶点数为奇数;(2)当G只有一个最大度点,且最大度等于它的阶减1,且H的最大度不大于它的阶减2,还得到了当G与H的最大度都分别不超过各自的阶减2时,G∨H的均匀全色数的一个上界。     

完全二部图的t-pebbling数

图G的t-pebbling数ft（G）是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列pebbling移动把t个pebble移到任意一个顶点上,其中的pebbling移动是从一个顶点上移走两个pebble,而把其中的一个移到与其相邻的一个顶点上,本文确定了完全二部图t-pebbling数,作为推论给出了完全K部图的t-pebbling数。     

扇与轮的联图F_m ∨ W_n的均匀全色数

对一个正常的全染色满足各种颜色所染元素数（点或边）相差不超过1时,称为均匀全染色,其所用最少染色数称为均匀全色数.就扇与轮的联图Fm ∨ Wn,得到了在m,n不同取值情况下的均匀全色数.     

图Pm∨Fn的均匀全色数

对一个正常的图的全染色满足各种颜色所染元素数(点或边)相差不超过1时,称其为均匀全染色,所用最少染色数称为图的均匀全色数.得到了路Pm与扇Fn的联图Pm∨Fn的均匀全色数.     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.     

完全二部图的点被多重集可区别的IE-全染色及一般全染色

利用反证法构造具体的染色方法, 讨论完全二部图的顶点被多重集可区别的IE-全染色及一般全染色, 给出最优染色方案, 并确定相应染色的色数.     

扇、轮和完全图的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪ E(G)到{1,2,…,k}的一个映射.如果(A)u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)∣u,v∈E(G)},称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全染数.文章讨论了扇与轮、完全图的多重联图的邻点可区别E-全色数.     

完全二部图全着色的构造

利用全着色矩阵给出完全二部图全着色的构造,该构造可以方便快捷对完全二部图进行全着色.     

星图和扇图的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同,则称它为图C的星K-全着色.图的全部星K-全着色中最小的数K称为它的星全色数.讨论了星图和扇图的广义Mycielski图的星全染色问题,得到了不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.     

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

研究若干联图的邻点可区别全染色,证明了:当n≥3时,χat(Kn∨Cn)=χat(Kn∨Pn)=2n+1;当n≥4时,χat(Kn∨Wn?1)=χat(Kn∨Fn?1)=χat(Kn∨Sn?1)=2n+1.     

完全2-分图的l-边-连通度

连通图G所谓的l-边-连通度（Z—edge—connectivity），就是使图C成为至少l个分支所必须去掉的最少边数，记作λl（G），即λ1（G）=min{｜E’｜：E’真包含E（G），ω（G—E’）≥l}．研究了完全2-分图的l-边-连通度，得到了定理：设G=G[V1，V2]是一个完全2-分图，｜V1｜=r，｜V2｜=s，r＋k=s，k≥0为整数．则图G的（k＋2）-边-连通度为（k＋1），即λk＋2（G）=r（k＋1）．     

一个特殊的双外平面图的全染色

双外平面图是一个平面图，它可以嵌入到平面上并使得它的顶点出现在两个面的边界上．设G是一个双外平面图，V(G)、E(G)、F(G)分别为双外平面图G的点集、边集和面集．G的全色数XT，(G)是使得V(G)∪E(G)中的任意相邻或相关联的两个元素均染不同颜色的最少颜色数．本文证明了最大度至少是6的2连通的特殊双外平面图G的全色数是△(G) 1，其中△(G)为G的最大度数．     

推广的Petersen图的相邻顶点可区分的全染色

图的全染色概念是点染色和边染色的推广,图的所有元素(顶点和边)都将染色且任相邻或关联的元素染色不同.邻点可区分的全染色是在正常全染色的定义上,使得相邻顶点的色集不同.本文给出了推广的Petersen图的相邻顶点可区分的全染色.