几类特殊图的条件色数

对整数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时,几类特殊图的条件色数。     

特殊图的条件染色

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

Wn⊙Pm和Cn⊙Sm的r-hued染色

图G和H的Corona乘积图记为G⊙H,它是复制一个图G以及复制|V(G)|个图H,把图G的第i个顶点跟复制的第i个图H的每个顶点相连.图G的(k,r)-染色是用k种颜色对图G进行正常染色，使得点v的所有邻点至少染min{r,d(v)}种不同的颜色，其中d(v)是图G中顶点v的度数.把图G的具有(k,r)-染色的最小正整数k称为r-hued色数，用χ_r(G)表示，通过对r-hued染色的定义，得到W_n⊙P_m和C_n⊙S_m的r-hued色数.     

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

当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-强全色数进行了确定.     

特殊平面图的集合色数

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

当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-强全色数进行了确定.     

关于一类联图的r-强边染色

单图G的r-强边染色是指图的距离不超过r的任意两点可区别的边染色，所谓两点u，v间的距离是指这两个点之间的最短路的长，记为d（u，v）．图G的r-强边色数x′s（G，r）表示．本文给出一类联图的2-强边色数的界，并将结论推广到r-强边色数的界．     

平面图的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.     

图的全-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通过某种操作得到的图。