平面图的3-hued染色

对于整数k,r0,图G的(k,r)-染色是一个正常k染色,使得对于每一个度数为d(v)的点v,v的邻点至少表现min{d(v),r}种颜色,这样的染色,称之为r-hued染色,图G的r-hued染色数,记作χ_r(G),是使图G存在(k,r)染色的最小的尼值.在这篇文章中,证明了,对于一般平面图G,χ_3(G)≤12.     

几类特殊图的条件色数

对整数k>0,r>0,图G的条件(k,r) 染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得：（1）相邻点获得的颜色不同;（2）|c(N(v))|≥min{|N(v)|,r}。G的条件色数是使得G有一个正常的(k,r) 染色的最小k值,记为χ_r(G)。本文主要研究了r取3时,几类特殊图的条件色数。     

Kn1,n2,n3,n4的点被多重集可区别的一般全染色(n1≤n23≤n4)

图G的一般全染色是指使用若干种元素对于图G的全体点及边的一个分配.通常情况下，染色时所用的k种颜色用1,2,…,k来表示，且数字代表的颜色之间有大小关系.图G使用了k种颜色的一般全染色叫作图G的k-一般全染色.利用反证法、构造染色法及色集合事先分配法，讨论了完全四部图K_n1,n2,n3,n4(n₁≤n₂3≤n₄)的点被多重集可区别的一般全染色.给出了最优染色方案，并确定了相应染色的色数.     

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

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

图的全-Domination染色

图G的一个全-domination染色是图G的一个正常点染色,使得G的每个顶点v控制除了v以外的至少一个色类,并且每一个色类被G中至少一个顶点控制。图G的全-domination染色所需的最少颜色数称为G的全-domination色数,记为χ_td（G）。本文通过图构造的方法证明了对于任意的图G和任意固定的整数k≥1,决定χ_td（G）=k是否是NP-完全的,并研究了χ_td（G）和χ_td（G^′）之间的关系,这里G^′是G通过某种操作得到的图。     

Kn□Km,s的r-hued染色

考虑完全图K_n 和完全二部图K_m,s的笛卡尔乘积图的r-hued色数. 首先, 根据正整数r 的不同值进行分类, 并结合K_n□K_m,s的性质, 刻画该图r-hued色数的下界; 其次, 找到K_n□K_m,s的一个具体的(k,r)\|染色, 并以此刻画该图r-hued色数的一个上界； 最后， 确定了K_n□K_m,s的r-hued色数.     

特殊图的条件染色

对于一个正整数r，图G的一个条件（k，r）-染色是使得图G的每个度至少为r的顶点至少与具有r种不同颜色的顶点相邻的正常的顶点染色．使图有一个条件（k，r）-染色的最小的整数k是图的第r个条件色数Z，（G），本文给出了对于不同的正整数，路、扇、轮的条件色数。     

条件染色正常图的几个充分条件

给定正整数r,图G的一个r-条件染色是G的顶点的一个正常染色,使得G中任意度数为d(v)的顶点v,其邻域中至少出现min{r,d(v)}种不同的颜色。若图的r-条件色数等于色数,则称图为r-正常的。给出了判断一个图G为正常图的一些充分条件,并用实例说明了这些条件并非必要的。     

K5,5,p的点可区别的IE-全染色（p≥2 028）

图G的IE-全染色f是指对?u,v∈V（G）,使得f（u）≠f（v）的一个一般全染色,其中u,v相邻,V（G）是图G的顶点集.设f是图G的IE-全染色,图G的一个顶点x在f下的色集合C（x）是指由x及x的关联边的颜色所构成的集合（非多重集）.若图G的任意两个不同顶点的色集合不同,则f称为图G的点可区别的IE-全染色（简记为VDIETC）.利用色集合事先分配法、构造染色法及反证法探讨了完全三部图K_5,5,p（p≥2028）的点可区别的IE-全染色问题,确定了K_5,5,p（p≥2028）的点可区别的IE-全色数.     

特殊平面图的集合色数

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

当24≤d≤34时圈的d-强全染色（英文）

对于图G=(V,E)的一个正常全染色,用C(v)表示图G的顶点v∈V的颜色以及与v关联的边的颜色构成的集合,称为点v的色集合.如果C(u)≠C(v),则u和v被该全染色所区别.一个图G的d-强全染色是指使得满足1≤d(u,v)≤d的任意一对顶点u和v可区别的一个正常全染色.所谓一个图G的d-强全色数是指对图G进行d-强全染色所需要的颜色的数目的最小值.对当d∈[24,34]时圈的d-强全色数进行了确定.     

图多彩染色中的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度点后多彩色数的变化。     

当35≤d≤55时圈的d-强全染色（英文）

对于图G=(V,E)的一个正常全染色,用C(v)表示顶点v∈V的颜色以及与v关联的边的颜色构成的集合,称之为点v∈V的色集合.如果C(u)≠C(v),那么就说u和v被该全染色所区别.一个图G的d-强全染色是指使得满足1≤dG(u,v)≤d的任意一对顶点u和v可区别的一个正常全染色.所谓一个图G的d-强全色数是指对图G进行d-强全染色所需要的颜色的数目的最小值.文中对当d∈[35,55]时圈的d-强全色数进行了确定.     

不含3圈和4圈的1-平面图是5-可染的

若图G能画到平面上,且允许每条边至多出现一个交叉点,则图G是1-平面图。图G的一个正常点染色是指存在一个顶点集到颜色集的映射φ:V(G)→{1,2,…,k},对于G中的任意两个相邻的点u和v,φ(u)≠φ(v)。图G的一个k染色是指图G能够正常点染色所需的色数至少为k,图G有一个k染色又称图G是k-可染的。通过权转移的方法证明了不含3圈和4圈的1-平面图是5-可染的。     

完全二部图K10,n(10≤n≤90)的点可区别E-全染色

图G的一个E-全染色f是指使相邻点染以不同颜色且每条关联边与它的端点染以不同颜色的全染色。对图G的一个E-全染色f,一旦∠u,v∈V(G), u≠v,就有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,则f称为图G的点可区别的E-全染色,简称为VDET染色。令χ^e_vt(G)=min{k|G存在k-VDET染色},称χ^e_vt(G)为图G的点可区别E-全色数。利用分析法和反证法,讨论并给出了完全二部图K_10,n(10≤n≤90)的点可区别E-全色数。     

关于图rK2∨K8的邻点可区别全色数

对一个简单图G的一个正常全染色，来说，G的点v的色集合C（v）是与v关联的边的颜色以及点v的颜色所构成的集合．对此f，如果G的任意两个相邻顶点的色集合不同，则称，为G的邻点可区别全染色．对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数．对图rK2∨K8的邻点可区别全色数进行了讨论．     

关于图rK2 ∨ Ks的邻点可区别全色数

对一个简单图G的一个正常全染色f来说,G的点v的色集合C(V)是与v关联的边的颜色以及点v的颜色所构成的集合.对此f,如果G的任意两个相邻顶点的色集合不同,则称f为G的邻点可区别全染色.对G进行邻点可区别全染色所需要的最少颜色数称为G的邻点可区别全色数.对图rK2∨K8的邻点可区别全色数进行了讨论.     

完全二部图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-全色数。     

树的D(r)-点可区别边染色

图G的一个正常边染色是指对G的每条边分配一种颜色使得任意相邻的两条边的颜色不同.图G的正常边染色f称为D(r)-点可区别边染色,如果对G中任意两个距离不超过r的顶点u,v∈V(G),有C'(u)≠C'(v),其中C'(x)={f(xy):xy∈E(G)}.图G的D(r)-点可区别边色数是指对图G进行D(r)-点可区别边染色所需要的最小色数,记为'r(G).文章讨论了树的D(2)-点可区别边染色及D(3)-点可区别边染色问题,通过逐层染色的方法,得到了树的D(2)-和D(3)-点可区别边色数的上界,并给出了线性时间的染色算法.另外,通过边染色与全染色的关系,得到了树T的D(3)-点可区别全色数不超过Δ(T)+3,D(2)-点可区别全色数不超过Δ(T)+2.     

子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色，且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值，记作χ^′_2-snd(G).采用反证法证明了：若图G是子立方图，则χ^′_2-snd(G)≤7.