二部图的[r,s,t]-着色

给出了二部图G的[r,s,t]-色数的界及它达到下界时的条件,讨论了星作为特殊二部图的[r,s,t]-色数,得到的结果为若G是二部图,v1,v2∈VΔ,v1v2E(G),u∈V,■u1∈NG(u),使得dG(u1)=1,且s≥2t,r≤t,则r,χs,t(G)=(Δ-1)s+1;若G是二部图,且r≥(Δ-1)s+2t,则r,χs,t(G)=r+1;若G是二部图,且(Δ-1)s+t<r≤(Δ-1)s+2t,则r,χs,t(G)≤(Δ-1)s+2t+1;若G是二部图,则rΔ+1≤r,χr,r(G)≤r(Δ+1)+1。

齿轮图_n的[r,s,t]-着色

在n阶轮图Wn=O1+Cn的轮圈Cn上每相邻两点之间都加入一个顶点所构成的图称为齿轮图,记为n.给出了齿轮图n的点色数、边色数和全色数,研究了齿轮图n当参数r,s,t满足一定件时的[r,s,t]-色数.

超图的[r,s,t]-着色

将一般图的[r,s,t]-着色推广到超图上得到超图的[r,s,t]-着色的定义及超图[r,s,t]-着色的一些性质和定理,并讨论了超图的[r,s,t]-色数的上下界。

图D_(m,4)的[r,s,t]-着色

由m个四回路恰有一个公共点构成的图记为Dm,4。研究图Dm,4的点着色、边着色和全着色,给出图Dm,4在参数r,s,t满足一定条件时的[r,s,t]-色数。

关于图的[r,s,t]-着色的几个结果

给定非负整数r,s和t,简单图G=(V,E)的一个[r,s,t]-着色是从集合V∪E到色集{0,1,2…,k-1}的映射c,使得对任意相邻的两点vi,vj有︱c(vi)-c(vj)︱≥r,对任意相邻的两边ei,ej,有︱c(ei)-c(ej)︱≥s,对相关联的任意点vi和边ej,有︱c(vi)-c(ej)︱≥t.图G的[r,s,t]-色数r,s,t(G)定义为使得图G存在[r,s,t]-着色的最小的整数k.本文给出了参数r=0和r=t=1的[r,s,t]着色的几个结果.

风车图K_3^((n))的[r,s,t]-着色

研究了风车图K3(n)的[r,s,t]-着色问题,给出了风车图K3(n)在一定条件下的[r,s,t]-色数.

树的[r,s,t]-着色

通过用树T的导出星K1,Δ(T)的一个[r,s,t]-着色对树T进行点、边着色,证明了树的[r,s,t]-色数等于树中最大导出星的[r,s,t]-色数.

带松弛条件的图的强边着色

给定两个非负整数s和t,图G的(s,t)-松弛强k边着色可表示为映射c:E(G)→[k],这个映射满足对G中的任意一条边e,颜色c(e)在e的1-邻域中最多出现s次并且在e的2-邻域中最多出现t次。图G的(s,t)-松弛强边着色指数,记作χ’(s,t)(G),表示使得图G有(s,t)-松弛强k边着色的最小k值。在图G中,如果mad(G)<3并且Δ≤4,那么χ’(1,0)(G)≤3Δ。并证明如果G是平面图,最大度Δ≥4并且围长最少为7,那么χ’(1,0)(G)≤3Δ-1。

稀疏图的(0,1)-松弛强边着色

给定一个图G=(V (G),E (G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′(s,t)(G).证明了在图G中,如果mad (G)<3,Δ≤7,那么χ′(0,1)(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g (G)≥7,Δ≥4,那么χ′(0,1)(G)≤{5Δ/2}.