关于弦图的色性

研究了n类弦图的色性,分别给出G=k_(n+1)[K_m]K_(m+1)[K_m]K_(m+1);图G含有K_(n+1)子图,G=K_(n+1)[K_m]K_(m+1)[K_m]K_(m+1)[K_m]K_(m+1);G=K_(n+1)[K_m]K_(m+1)[K_l]K_(l+1)的充分必要条件。     

弦图上团划分数问题的复杂性

本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。     

关于图的色性

本文引进了一个新的记号,研究色多项式的根全为非负整数的图的色性。     

图的团分解

该文证明了从任何一个ｎ阶图中一个接一个地移去最大团，则移去团的顶点和达ｎ＾２／２后是空图，从而证明了Ｗｉｎｋｌｅｒ猜想。     

关于完全三部图色唯一性的判定

G是简单图,用P(G,λ)表示图的色多项式.若对任意简单图H当P(H,λ)=P(G,λ)时,都有HG,则称G是色唯一图.Liu R.,Zhao H. X.和Ye C.已经证明:当n和k为整数且满足n≥k 2≥4,完全三部图K(n-k,n,n)是色唯一的;当n和k满足n≥2k≥4时,完全三部图K(n-k,n-1,n)是色唯一的.在本文中,证明了当k是奇数且n≥k2/4 15/4≥6,或k是偶数且n≥k2/4 4≥5时,完全三部图K(n-k,n-2,n)是色唯一的;当k是奇数且n≥k2/4 19/4≥7,或k是偶数且n≥k2/4 5≥9时,K(n-k,n-3,n)是色唯一的.     

关于图的星色函数

图的星色函数是研究星染色的一个重要函数.给出几种重要图类的星色函数,讨论星色函数的一些基本性质,提出几个值得进一步研究的问题.     

一类具有整根色多项式的图的色等价类

用P(G,λ)表示简单图G的色多项式,文章采用数学归纳法刻画了一类具有整根色多项式图的结构特征为P(G,λ)=λ(λ-1)(λ-2)m(λ-3)…(λ-n+1)(n≥3,n,m∈Z+),从而证明色等价类[G]中的图都是弦图.     

关于图的色性

本文引进了一个新的记号,研究色多项式的根全为非负整数的图的色性。     

关于连通点可迁图的色性

Chia G L在1986年提出了这样1个问题:所有连通点可迁图是否是色唯一的?本文给出了一族连通点可迁图,它们都不是色唯一的,否定地回答了这个问题。     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

关于图全着色的几个结果

引入了一种研究图全着色问题的新方法，即从考虑图中的圈出发研究全着色问题．运用该方法确定了一些图的全色数，并给出了图全色数的一个上界．     

关于递推团图直径的PRS-猜想

本文证明了存在一个图G 使得它的直径与其n-次团图K~n(G)的直径满足关系。diamK~n(G)=diamG n其中n≥1为整数,这就是所谓PRS-猜想。     

关于不可约的图

图的色唯一性与补图的各分支的不可约性密切相关。用P_n表示n阶路,把K_3的一个项点与P_n-2的一个一度点重迭后得到的图记为D_n。本文分别得到了D_n和P_n是不可约图的一千充分条件,并且给出了一批不可约的D_n和P_n。     

几类平面图的分数染色

图G的一个分数染色是从G的独立集的集合ζ到区间[0，1]的一个映射c，使得对任意顶点x，都有∑s∈ζ,s,1 x∈s c(s)≥1，将此分数染色的值定义为∑s∈ζ c(s)．图G的分数色数xf(G)是它的所有分数染色的值的下确界,讨论了几类平面图的分数色数。