Klein瓶上的6-正则嵌入图的着色性质

Brooks证明了:若G是连通的简单图,并且它既不是奇圈,又不是完全图,那么它的色数至多为△(G),其中△(G)为图G的最大度.它可以推出嵌入到Klein瓶上的任意的一个6-正则图的色数至多为6.通过对Klein瓶上的6-正则嵌入图的结构分析,证明了Klein瓶上的任意的一个6-正则嵌入图的色数为5.     

关于扇和完全等二部图联图的点可区别边染色

通过结构分析的方法,考虑各种不同情况,给出了一类联图的点可区别的边染色方法,并得到了它的点可区别的边色数.     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

图的邻点可区别全染色的渐近性质

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同,其所用的最少颜色数称为邻点可区别全色数.张忠辅老师猜想:对于|V(G)|≥3的连通图G,其邻点可区别全色数最多不超过△(G)+3.用概率方法证明了对简单图G,△≥14,有χ_(at)(G)≤△+C,其中C≥10~(26)+1.     

Pm∨Sn的邻点可区别全染色

把星{u0,u1,u2…,un}中的每一个点与路{v1,v2,v3,…,vm}中的每一个点相连,得到路和星的联图,记为Pm∨Sn.本文给出了Pm∨Sn的邻点可区别全色数.     

图的邻点可区别全色数的一个上界

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同．本文用概率方法得到了邻点可区别全色数的一个上界．     

关于扇和完全等二部图联图的边染色

得到了扇和完全等二部图联图的边色数.     

完全二部图的广义Mycielski图的全染色与边染色

为了找到Km,n图的广义Mycielski图的全色数与边色数,用分析的方法,考虑不同情况,给出了它的全染色法与边染色法,得到了它的全色数与边色数.     

完全二部图广义Mycielski图的邻点可区别全色数与邻强边色数

得到了完全二部图Km,n的广义Mycielski图Ml(Km,n),当(l≥1,n≥m≥2)时的邻点可区别全色数与邻强边色数.     

关于D(F_n)和D(W_n)的点关联邻点可区别全色数

对简单图G(V,E),f是从V(G)∪E(G)到{1,2,…,k}的映射,k是自然数,若满足:1)uv,uω-∈E(G),v≠,-ωf(uv)≠f (uω-);2)uv∈E G,C(u)≠C(v).则称f是G的点关联邻点可区别全染色法,其所用到的最少颜色数称为图G的点关联邻点可区别全色数.这里C(u)=f(u)∪f(uv)uv∈E(G).得到了扇和轮的倍图的点关联邻点可区别全色数.