完全正则m-元树的Hamiltonian色数与最小Hamiltonian着色

对一个n阶连通图G,G的Hamiltonian着色(以下简称G的H着色)定义为从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,且对G的任意2个不同顶点u和v,满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对G的一个H着色c,将Max{c(u)|u∈V(G)}称为c的值,记作hc(c)。将Min{hc(c)|c是G的H着色}称为G的Hamiltonian色数(以下简称G的H色数),记作hc(G)。如果G的一个H着色c满足hc(c)=hc(G),则称c为G的一个最小H着色。本次研究得到了完全正则m-元树的H色数的确切值,并给出了其最小H着色。     

边染色图中的2-因子

令G是含n个点的边染色图,对G中任意顶点x,定义其色邻域CN(x)为集合{c(xy)|xy∈E(G),y∈V(G)}。如果G中任意相邻的两条边都染有不同的颜色,就称G是正常染色的。证明了如果边染色图G满足对V(G)中任意两点u,v有|CN(u)∪CN(v)|≥4n/3+8,则图G含有一个正常染色2-因子。     

特殊平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点v,与v相邻的顶点所着颜色的集称为v的邻色集,记为NC(v)。如果G中任意相邻的两个顶点u,v满足NC(u)≠NC(v),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记为χs(G)。本文给出了与轮图有关的一类平面图的集合色数,向日葵图和风车图的集合色数,最后给出了一个猜想。     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.     

完全二部图K_(4,n)(n≥47)的点可区别E-全染色

G是一个简单图,G的一个E-全染色f是指使相邻顶点着不同颜色且每条关联边与它的顶点着以不同颜色的全染色。设f为G的一个E-全染色,对任意x∈V(G),用C(x)表示在f下顶点的颜色以及与x关联的边的颜色所构成的集合。若任意u,v∈V(G),u≠v,有C(u)≠C(v),则称f是图G的点可区别的E-全染色,简称VDET染色。图G的VDET染色所用颜色数目的最小值称为图G的的点可区别E-全色数或简称VDET色数,记为χ_vt~e(G)。讨论并给出了完全二部图K_(4,n)(n≥47)的点可区别E-全色数。     

无相交三角形平面图的邻点可区别边染色

图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'_a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'_a(G)≤max{Δ(G)+2,10}。     

点可区别边色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.     

Wm与Pn(n≤3)联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E(G)到{1,2,…,k}的映射,且满足V u,v∈V(G),u≠v,有S(u)≠S(v),其中S(u)={f(uw)|uw ∈E(G)}.数min{k|G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs(G),研究了WmVPn(n≤3)的点可区别边染色,给出了WmVPn(n≤3)的点可区别边色数.     

完全二部图K_(9,n)的点可区别IE-全染色(英文)

G是一个简单图,G的一个IE全染色f是一个映射,该映射满足:对u,v∈V(G),u≠v,有C(u)≠C(v).图G的一个点可区别IE-全染色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)},简称k-VDIET.数min{k:G有一个k-VDIET染色}称为图G的点可区别IE-全色数或简称VDIET色数,记为χievt(G).本文讨论并给出了完全二部图K9,n的点可区别IE-全色数.     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.