一类整数距离图的分数色数

利用整数距离图的结构特征,研究当m<2k时,G(Z,Dm,k,t)的分数色数(其中Dm,k,t={1,2,…,m}-{k,k+1,…,k+t}),并给出在k>t,m≥2k条件下G(Z,Dm,k,t)的分数色数,以及当k>t,m=2k+i,0≤i≤2t-1时,G(Z,Dm,k,t)的色数.     

两类距离图的分式色数和点色数

分式色数和,点、色数是图的两个重要参数.本文在文献[1]的基础上给出了两类距离图G(Z,Dm,k,k+1)与G(Z,Dm,kk+1,K+2)的分式色数和点色数.     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

关于图与其补图谱半径之和的又一上界

给出了图与其补图谱半径之和ρ(G) ρ(G)的新上界,对任一顶点数为n,边数为m的简单图G,若其色数为k,则有ρ(G) ρ(G)^c≤2的平方根(n(n-1)-（2m／k 2m^-／k^-))^1／2,其中k^-,m^-=1/2n(n-1)-m分别表示G^c的色数、边数。从而改进了已有的结果。     

一个新的激活策略在偏κ—树上的应用

笔者使用一个新的激活策略证明了 ,如果G是一个偏k -树 ,其色数为r=k + 1 ,缺陷度d≥ 2k + 1 ,那么 ,对这个 (r,d) -松弛竞赛染色 ,Alice有一个赢的策略。这个结果可以写为 ( 2k+ 1 ) - χg(G)≤k+ 1 ,它是文献 [3]中相应结果的一个改进     

图的色数与着色数的上界

证明了对于围长不少于2k1的图G,其色数X(G)≤c((bk,2k+1+2)n)1/k+1+2,其中c=c(k)且limk→∞ c(k)=1,bt,k是G的booksize.另外还证明了对于围长不少于2k+1的图G,其着色数σ(G)≤[bk,2k+1+1)n/2]1/k+2.     

不含某些图作为导出子图的图的色数

Erods证明了对于任意一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要讨论一类特殊的F-free图的色数和团数的关系。设图G=(V,E)是一个不含K1,k+1+e、C4和C4+e为导出子图的连通图,不是星图和奇圈。若α(G)≥k≥3,则χ(G)≤(k(k-1)/2)ω(G)。     

三部图K(m,n,r)-A(|A|=2)的色唯一性

设G是简单图,用P(G,λ)表示图G的色多项式,令K(m,n,r)表示完全三部图.证明了1)当3≤m≤n≤r时,令s=1/√6√(n-m)2 (r-n)2 (r-m)2 12,若m n r＞2√3s 3s2,则K(m,n,r)-A(|A|=2)是色唯一图;2)当m≥4时,K(m,m,m)-A,K(m,m,m 1)-A,K(m,m 1,m 1)-A,(|A|=2)都是色唯一图;3)设n,k为非负整数,则当n＞k2 2√k2 6 k 2时,K(n-k,n,n)-A;当n＞k2 2√k2 6-k/3 2时,K(n,n,n k)-A;当n＞2√3k2 6 k2 2时,K(n-k,n,n k)-A(|A|=2)均为色唯一图.     

独立集中具有最小特定度和的点的上可嵌入图类(英)

结合边连通度，探讨了独立集中具有最小特定度和的点的上可嵌入图.得到了下列结果. (1)设G,是一个2-边连通简单图且满足条件:对任意一个G的3-独立集I, ∨x_i ,x_j ∈I (i,j = 1,2,3), d(x_i ,x_j)≧3 (1 ≦ i ≠ j ≦ 3) =>∑_{i = 1}³ d(x_i) ≧ v + 1(v = | V(G)|}), 则G是上可嵌入的;(2)设G是一个3-边连通简单图且满足条件:对任意一个G的6-独立集I, ∨x_i ,x_j ∈I (1≦i,j≦6), d(x_i,x_j) ≧3(1 ≦ i ≠ j ≦ 6) => ∑_{i = 1}⁶ d(x_i) ≧ v + 1(v = | V(G)|), 则G是上可嵌入的.     

关于Frobenius度量的推广

把Frobenius度量d_F(Z,W)推广到一般的酉不变度量d_p, _(k) (Z,W). 对于 p≥2 推导了它的具体表达式,对于 1 ≤ p <2给出猜测, 并对 p =1 ,l=2的情况给出证明．     

I(Cn)的圆色数

讨论了n-圈Cn的关联图I(Cn)的结构性质.证明了I(Cn)是4-正则的平面图并研究了其色数.主要研究I(Cn)的圆色数并得到结果:如果n=3m,则χc(I(Cn))=χ(I(Cn))=3;如果n=3m 2,则χc(I(Cn))=(6m 4)/(2m 1).当n=3m 1时,给出了χc(I(C3m 1))的一个界.     

两类图的点可区别边染色数

证明了,任意正整数k≥2,存在点可区别边色数为2k+1的k+1-正则图;任意正整数m≥4,存在点可区别边色数为m的偶图.     

mK的点可区别全染色mK的点可区别全染色

 利用色集事先分配法, 借助于矩阵构造具体染色及递归法的方法, 研究图的点可区别全染色问题, 给出了m个K4的点不交的并mK4的点可区别全色数χvt(mK4)的确切值, 即“如果k-14<4m≤k4, m≥2, k≥6, 则χvt(mK4)=k”. 验证了VDTC猜想对mK4成立.     

图P_n~k的着色

设k是一个正整数,在含有n个顶点的路Pn=v1v2…vn上,当且仅当两点的距离为k(k≥2)时增加一条边,这样所得到的图叫做Pnk(v1,vn),有时Pkn(v1,vn)也简记为Pnk.论文研究图Pnk的点着色、边着色和点、边全着色,得到图Pnk的点色数、边色数和图Pnk满足点、边全着色猜想等结论.     

关于联图W_m∨P_n的均匀全染色

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

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

色数与谱半径和生成偶子图

设G为n≥1 阶简单无向图,ρ(G)和μ(G)分别表示图G的邻接谱谱半径和Laplacian谱谱半径.利用生成偶子图证明了：当k为偶数时,ρ(G)≤（k-1）/kμ(G);当k为奇数时,ρ(G)≤k/（k+1）μ(G).其中k(≥1)为简单图G的色数.     

默森尼质数的判别法及其构造

得到默森尼 (Mersenne)数为质数的判别法和构造 ,当Mp=2 p- 1为合数时其因数的特征及其因数个数的估计。(1)Mp=2 p- 1为质数的充要条件是 Mp2kp + 1≡ 0　 (mod p)(2 )如果Mp=2 p- 1且Qi|Mp　i=1,2 ,……T那么 12     

图Pm×P3(n=11+8k)的点可区别全染色与算法

集合{1,2,…,n}中取4个数字的所有组合,经三角排序后任意相邻2个组合都有3个相同数字.利用此结果和组合性质(n+8k3)-(n3)≡0 (mod 4)构造算法,并证明当n=11+8k(k =0,1,…)和(n-14)/2+2＜m≤(n4)/2+2时积图Pm×P3的点可区别全色数为n.     

图的相邻强边着色数

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G) 1.