设k和d是两个正整数，并满足k≥2d，图G的一个(k，d)-染色是指映射：f：V(G)→Zk={0，1，…，k-1}满足对任意uv∈E(G)，均有|f(u)-f(v)|k≥d，其中|x|k=min{|x|，k-|x|}.称x*(G)=inf{k/d：G存在(k.d)-染色}为G的星色数. 图G的星色数(又称圆色数)x*(G)是A.Vince在1988年提出的，它是图的点染色的自然推广.在星色数领域一个很重要的问题是确定图的星色数是否与色数相等，这是一个NP问题.到目前为止人们只对几类特殊的图证明了相应的结果，这其中Mycielski图是很受关注的一类.本文第二、三章关注的是完全图的Mycielski图的星色数问题，围绕猜想1.1：若n≥t+2，则x*(Mt(Kn))=x(Mt(Kn))=n+t，其中Mt(Kn)=M(Mt-1(Kn))展开研究，并得到了最新的结果.第四、五章分别得到了一类平面图的星色数和星色数的一个上界. 本文共分为四章.第一章介绍了星色数的背景和相关的记号、结论.作者首先陈述了星色数的定义、性质和已经取得的成果，以及现在所面临的一些问题，并引出了本文所要关注的问题：完全图的Mycielski图的星色数.然后就这个问题给出了一系列预备知识和结论，包括Mycielski图的点的标号系统、Mycielski图星染色的性质等，这些结果在下文的证明中将会用到. 第二章中作者提出根点有向图、有序三元集、3-断集等概念，探讨了这些概念的性质，以及相互之问的关系，并得到了完全图的Mycielski图的星染色与其根点有向图的有序三元集之间的联系，最后证明了：定理2.1t≥1，n≥11/122t-1+2t+1/3.则x*(Mt(Kn))=x(Mt(Kn))=n+t.第三章主要通过对K5，K6的3-阶Mycielski图星染色的性质进行讨论证明了：定理3.3n≥5时，x*(M3(Kn))=x(M3(Kn))=n+3，即猜想1.1在t=3时成立. 这部分证明较为繁琐.最后给出了两个与猜想1.1等价的次级问题，可作为解决该猜想的一个思路：猜测1：t≥1，n≥t+2，若x*(Mt(Kn))=x(Mt(Kn))=n+t，则x*(Mt(Kn+1))=x(Mt(Kn+1))=n+t+1猜测2：t≥l，则x*(Mt(Kt+2))=x(Mt(Kt+2))=2t+2第四章我们由轮图出发定义了一类平面图，并求出了它们的星色数：定理4.1设k=min{ki：ki为奇数，1≤j≤n}，则x*(Wn，[ki]={2ki为偶数，1≤i≤n;2+2/kk1=…=kn=k，k，n均为奇数；2+1/k+1其它. 第五章讨论图的星染色的伴随有向图Df(G)与星色数f之间的关系，得到了[13]中一个结论的推广，从而可以通过图的星染色的伴随有向图得到图的星色数上界： 定理5.1非偶图G有(k，d)-染色f.使得Df(G)无有向图，设p为Df(G)中有向路的集合，(V)P∈p，z(P)为P上染0，1，…，d-1色的点数，t=max{z(P)+1：P∈p}，则x*(G)≤k/d-1/td.