图Pkn的着色

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

广义Petersen图GP(n,k)的着色

本文研究广义Petersen图GP(n,k)的点着色、边着色和点-边全着色,得到广义Petersen图GP(n,2)的点色数、边色数和全色数,同时还得到当n为偶数,k为奇数时,该广义Petersen图GP(n,k)满足点-边全着色猜想等结论.     

星和扇上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义Mycielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i 1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}.在这篇文章里,我们讨论了星和扇上的锥的D(2)-点可区别的正常边染色,并给出了相应色数.     

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)=｛v0i|i=1,2,…,p｝的简单图,n是正整数, 称Mn(G)为G上的锥(或广义Mycielski图),如果 V(Mn(G))=｛v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w｝, E(Mn(G))=E(G)∪｛vijv(i+1)k|v0jv0k∈E(G), 1≤j, k≤p,i=0,1,…,n-1｝∪｛vnjw|1≤j≤p｝。 讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。     

P_n~k和T_((k_1,k_2,…,k_n))的色多项式

本文研究了图Pnk和T(k1,k2,…,kn)的色多项式,得到P2n、P3n和T(k1,k2,…,kn)的色多项式递推公式,以及Pn2仅当n≤4时是色唯一图,T(k1,k2,…,kn)仅当n=1是色唯一图等结论.     

一类树关于能量的排序

图G的能量E(G)定义为图G的所有特征值绝对值的和.令Tn(n≥4)是由路Pn=v1v2…vn的顶点v2与一个悬挂点联结得到的图,Tn(vi)1是由路Pn=v1v2…vn的顶点v2与vi分别联结一个悬挂点得到的图.将Tn(vi)1简记为n(2,i)1,完全解决了树n(2,i)1依能量排序的问题,它可以按n模4同余区分为4种不同情形.文中给出结构类似的树n(2,i)k1k2依能量排序的一般规律与n(2,i)1的能量排序完全类似的猜想.     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

图K_(2n)\E(F_5)(n≥13)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(F5)(n≥13)的点可区别边色数.     

两类平面图的关联色数

轮 Wr 1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图.新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边.所谓花图Fr,m,n(r≥3,m≥1,n≥2m 1),是在轮Wr 1中的在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图.所谓棱柱Qn(n≥3),是指Qn=(V,E),y={u1,u2,…,un}U{v1,V2,…,vn},E={uiui 1,vivi 1,uivi,u1vi 1|i=1,2,…,n},其中un 1=u1,vn 1=v1.通过给出花图Fr,m,n>(r≥3,m≥1,n≥2m 1)和棱柱Qn(n≥3)的一种关联着色方法,确定了它们的关联色数.     

链状割点图的Hosoya多项式

任一连通图的Hosoya多项式的定义如下:H(G)≡H(G,x):=∑d(G,k)xk k≥0,其中d(G,k)是图G中距离为k的点对的个数。事实上,d(G,0)等于图G的点数,而d(G,k)等于图G的边数。设{Gi}ni=1是一个两两不交的图的集合,并且Vi,Vi∈V(Gi),所谓链图C(G1,G2,…,Gn)≡C(G1,G2,…Gn;v1,w1,v2,w2,…,vn,wn)指的是将各点对wi和vi+1粘合起来而得到的图,其中i=1,2,…,n-1。文章得到了链状割点图的Hosoya多项式,并且,作为引理,并给出了树的Hosoya多项式。     

关于平面图的边面全着色

定义了平面图的边面全色数，提出了相应的猜想，证明了无割点外平面图的最大度不少于７时，其边面全色数等于其最大度。     

较少短圈的平面图的全色数

图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。     

完全二部图K5,n的点可区别IE全染色

设G是简单图, 图G的一个k 点可区别IE 全染色(简记为k VDIET染色) f是指一个从V(G)∪E(G)到｛1,2,…,k｝的映射, 且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G), u≠v, 有C(u)≠C(v), 其中C(u)=｛f(u)｝∪｛f(uv)|uv∈E(G)｝。 数min｛k|G有一个k VDIET染色｝称为图G的点可区别IE 全色数,记为χievt(G)。本文给出了完全二部图K5,n(n≥6)的点可区别IE 全色数。     

P_m∨F_n(m=1,2,3,4,n+1)的点可区别均匀边染色

图G的一个正常边染色如果满足任意两个不同点的关联边色集不同,且任意两种颜色所染边数目相差不超过1,则称为点可区别的边染色,其所用的最少的颜色数称为图G的点可区别均匀边色数.运用组合方法研究联图Pm∨Fn的点可区别完全均匀边染色,得到当m=1,2,3,4,n+1时的Pm∨Fn的点可区别均匀边色数.     

图多彩染色中的2度点删除问题

对整数r0,图G的一个r-多彩染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)︱c(N(v))︱≥min{N(v),r}(其中N(v)代表v的邻点集)。使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。     

点关联较少3-面的平面图的全染色

证明了对每点至多关联2个3-面的平面图，全染色猜想成立. 对每点至多关联2个3-面且Δ(G)≥8的平面图，有x_T(G)=Δ(G)+1.对每点至多关联[Δ(G)/2」个3-面且Δ(G)≥9的平面图，有x_T(G)=Δ(G)+1.     

幂图的点强全色数

图G的一个正常全染色称为图G的点强全染色,当且仅当N[v]中任意元素都染有不同的颜色,其中N[v]={u}uu∈E（G）}U{u},图G的点强全染色所用颜色的最少数目称为图G的点强全色数．文章通过研究幂图t的结构性质,利用穷染、置换的方法,研究了幂图礴的点强全色数,并给出了一种具体的染色方案．