论文部分内容阅读
一个图G的圆色数Xc(G)是图G的色数X(G)的自然推广，最初是由Vince于1988年以“星色数”的定义提出来的.朱绪鼎在文献[3]中用类似Hajos定理的一些操作，利用Gdk的复制，构造了所有圆色数至少是k/d的图，k/d≥3.该文利用此文献中的三种操作构造了圆色数相等的一类图，计算出结果图S1，S2，S3[3]的圆团数，在此基础上给出S1，S2，S3[3]为圆不完美的充分条件，同时给出如下定理[3]的简化证明：如果r≥3，G1，G2，…G7是圆色数至少为r的图，则Xc(S3)≥r。文章的最后给出了圆色数的另一等价定义：任意图G，Xc(G)=min{k/d｜2d≤k≤｜V(D)｜且k,d(G)≤k/d}.(其中D是G的定向图)