树的星边染色

研究了树的星边染色,确定了两类特殊树的星边色数,并得到了一般树的星边色数的一个可达上界。     

齿轮图的星边染色

图的星边染色是一个正常边染色且满足任意2种颜色导出的连通子图为长度不超过3的路.利用反证法和组合分析法讨论了齿轮图的星边染色,通过构造具体染色得到了齿轮图的具体星边色数.     

一类仙人掌图的星边染色

图G的星边染色是指G的一个正常边染色,使得G中任一长为4的路和长为4的圈均不是2-边染色的.图G的星边色数χ’ _st(G)表示图G有星边染色的最小颜色数.仙人掌图是一个连通图使得每个块是圈或者边.利用数学归纳法得到了一类仙人掌图C_n·C_m(n≥3,m≥3)的星边色数,从而推广已知结果 .     

圈龙图的星边染色

通过分析圈龙图的结构,利用组合分析法及反证法讨论了圈龙图的星边染色,通过构造具体染色得到了圈龙图的星边色数.     

d-维网格的星边染色

研究图~$G$\,的星边色数~$\chi_{s}^{\prime}(G)$\,与其顶点数~$\nu$ 和边数~$\varepsilon$\,之间的关系. 证明了当~$\Delta(G)\geqslant2$\,时, 有~$\lceil\frac{8\varepsilon}{3\nu}\rceil\leqslant\chi_{s}^{\prime}(G)$. 得到了~$2$-维网格的星边色数, 并且给出了超立方体和~$d$-维网格的星边色数的可达上界和下界.     

联图P_m∨P_n的星边染色

给出了联图Pn∨P2的星边色数和联图Pn∨Pn,Pm∨Pn星边色数的上界,同时也给出了一种简单易行的星边染色方法.     

最大度为3的2-连通外平面图的星边染色

如果图G中没有长为4的路是2-边染色的,那么称图G的一个正常边染色是星边染色的.使得G有星边染色的最小颜色数称为G的星边色数,记作X1s(G).研究了最大度为3的2-连通外平面图的星边染色,证明了4≤X1s(G)≤6,确定了一些特殊外平面图的星边色数.     

几类r-冠图的星边染色

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数.     

不含4-,5-圈且无相交3-面的平面图的星边染色

图G的星边染色是指G的一个正常边染色满足G中无长为4的路(或圈)是2-边染色的.使得图G有星边染色的最小颜色数k称为G的星边色数,记为χ_st^′(G).证明了若平面图G不含4-5-圈且无相交3-面,则χ_st^′(G)≤[1.5Δ]+10.     

一类有向图的星边弧染色

提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为(→x)s′(D).运用Lovász局部引理证明了若有向图D=(V,A)的最大出度△+与最大入度A-满足线性关系△+=k△-(△(D)≥7,k＞0),则(→x)s′(D)≤16[(√1+k2)/1+k△3/2]*,这里[*]*表示上取整.     

完全图和星的合成的点可区别正常边染色(英文)

首先,给出了完全图K_p和星S_q的合成的点可区别正常边色数的一个上界:当p≥2,q≥4时,上界是pq+1.再利用正多边形的对称性以及组合分析的方法来构造染色,分别得到了当p=2,q≥4;p≥3,q=4;p是偶数且p≥4,q=5;pq是奇数且p≥3,q≥5时,完全图K_p和星S_q的合成的点可区别正常边色数.     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

图的边覆盖染色与分数边覆盖染色

讨论了图G=(V,E)的分数边覆盖色数χ′cf(G)的概念和性质,给出计算χ′cf(G)的一个精确公式,即χ′cf(G)=minS2·|C[S]||S|+1,其中S为V(G)的非空子集且|S|为奇数,C[S]是E(G)的至少有一个端点在S中的边构成的子集,并证明δ-1<χ′cf(G)δ;同时讨论了χ′cf(G)与图G的边覆盖色数χ′c(G)的关系,并利用χ′cf(G)与χ′c(G)的关系对图进行分类.     

图K_(2n)\E(K_(1,5)))(n=10,11)的点可区别边染色

讨论了图K2n\E(K1,5))(n=10,11)的点可区别边染色,得到图K2n\E(K1,5))(n=10,11)的点可区别边色数为χvd′(K2n\E(K1,5)))=2n.     

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图,其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖,如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ,由此将 χ’c(G)=δ的图称为CⅠ类图,否则称为CⅡ类图. 显然,图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件,而且该条件中的下界是最好的。     

-K3V Kn 的Smarandachely邻点可区别正常边染色

图的染色问题是图论研究的主要内容之一,起源于著名的"四色猜想"问题.图G的一个正常边染色f称为是Smarandachely邻点可区别的,如果对G中任何相邻的两个顶点u与v,与u关联的边的颜色的集合和与v关联的边的颇色构成的集合互不包含.对一个图G进行Smarandachely邻点可区别正常边染色所用的最少颜色数称为G的...     

若干特殊图的广义字典积的星全染色

设G是具有顶点集y（G）={t0,…,t,1}（n≥2）的图,hn=（Hi）i∈0,1…n-1}是不相交图的序列,其中Hi的顶点集为V（Hi）={（ti,y1）,…,（ti,yx},x≥1.文中用构造染色集的方法,研究得到了若干特殊图的广义字典积G[hn]的星全色数.