图Pkn的着色

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

图P_n~k的着色

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

完全图迭线图的1—因子分解

证明了完全图片K_n的K(≥1)次迭线图L~k(K_n)有1-因子分解当且仅当L~k(K_n)的点数为偶数。     

图的平均距离的一点注记

给出了完全二分图Km,n,Km^-∨Pn,Km^-∨Cn的平均距离的计算公式。     

一类星染色的临界图

研究了图的星染色的临界图的性质，得到了x^*临界图的一些必要条件和充分条件，并给出一类星染色的临界图，它在星染色中的作用如同正常染色中的完全图。     

关于图的广义Mycielski图的邻点可区别关联着色

邻点可区别关联着色是使得相邻顶点的颜色集不同的关联着色。主要研究了路,圈C3m, C4m与完全图的广义Mycielski图的邻点可区别关联色数, 拓展了图着色的领域,便于更好的研究图的结构。     

系列并行图,4阶完全图与小树宽图

给出了树宽≤2的图也就是系列并行图的几个等价刻画。证明了对有限图G(可以有环有重边)以下四断言彼此等价:(1)G是系列并行图,(2)G的任一个minor至少有一个点的度≤2;(3)G不以4阶完全图为minor;(4)G无子图同胚于4阶完全图。     

一般图的不交路划分问题

给定一个阶为n的简单图G=(V；E)，其中α(G)≥4，及1个正整数k≥2，考虑在领域条件下G划分成k条点不交路的问题，并得到下面的结果：对G中任何4个独立点x1，x2，y1，y2，满足领域条件，1NG(x1)∪NG(x2){ }NG(y1)∪NG(y2)1≥n-k-1，则要么G能划分成k条点不交的路，要么G属于一类例外图G′。     

图的对策着色和对策色数

图的对策色数Ⅱ Xg(G)是由图的点色数Xg(G)拓展得到的。本文给出了一些图的对策色数,并讨论了图的对策色数的性质。     

关于图的L(3,2,1)-标号问题

图G的L(2，1)-标号是一个从顶点集V(G)到非负整数集的函数f(x)，使得若d(x，y)=1，则|f(x)-f(y)|≥2；若d(x，y)=2，则|f(x)-f(y)≥1．图G的L(2，1)-标号数A(G)是使得G有max{f(v)：v∈V(G)|=k的L(2，1)-标号中的最小数k．将L(2，1)-标号问题推广到更一般的情形即L(3，2，1)-标号问题，并得出了全图、块图的L(3，2，1)-标号数的上界．     

半群Cayley图的保色点传递性

讨论半群Cayley图的保色（弱）点传递性,得到保色弱点传递的Cayley图是保色点传递的充要条件,并给出满足此条件的半群类.     

2-连通P3-支配图的Hamilton圈

如果图G中任意一对距离为2的顶点x,y,有J(x,y)∪J′(x,y)≠Φ,则称G为P₃-支配图。本文证明了：设G是n(≥3)阶2-连通P₃-支配图,如果对G中任意一对不相邻的顶点x,y,有2|N(x)∪N(y)|+d(x)+d(y)≥2n-5,则G含有Hamilton圈或者G∈{K_2,3,K_1,1,3}。     

关于完美3—全图的一点注记

得到３－全国含有奇洞的充要条件,完美３－全图是ｋ是染色的充要条件及３－全图是连通的充要条件。     

关于图的边添加

给定任意正整数t和d(≥2),记P(t,d)为在直径d的路上加上t条边后所得图的最小直径.证明了:P(6,4)=1; 当d=5,6,7时有P(6,d)=2;当d=7(2k-1)+h(k≥1, 1≤h≤14) 时有(d)/(7)≤P(6,d)≤ (d)/(7)+2若h=7;(d)/(7)+1其他;当d=5,6,7,8时有P(7,d)=2;当d=8(2k-1)+h (k≥1,1≤h≤16)时有(d)/(8)≤P(7,d)≤ (d)/(8)若h=1;(d)/(8)+2若h=2,3,4,5,6,7,8;(d)/(8)+1其他.     

一类2-稀疏图的补图的L(2,1)-标号

构造了洞指数ρ(G)≥1的一类2-稀疏连通图的补图的两个不同的岛序列。     

轮和路的广义Mycielski图的星全染色

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

等广义联图的Mycielski图的星全染色(英文)

研究了一些等广义联图的Mycielski图的星全染色,并得到了它们的星全色数。     

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

研究了若干广义Petersen图G(n,r)的邻点可区别全染色。 构造性地证明了:若n≡0(mod 4),r0(mod 4)或n≡0(mod 5),r0(mod 5),则G(n,r)的邻点可区别全色数为5。     

若干Hamming距离图的邻点可区别全染色

一个正常的全染色满足相邻点的点染色及关联边的色集不同时,称为邻点可区别全染色,其所用最少染色数称为邻点可区别的全色数。文中研究了一些Hamming距离图的邻点可区别全染色。