圆色数和圆不完美图

摘要

一个图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的定向图)

目录

学位论文独创性声明和使用授权声明

摘要

第一章绪论

第二章前言

§2.1基本概念

§2.2图的圆色数

§2.3 已有的相关结论

第三章Gdk图，Hajós构造

§3.1 Gd k图的定义和性质

§3.2 Hajós构造

第四章本文的主要结果

§4.1构造一类圆色数相等的图

§4.2圆不完美图

§4.3圆色数的另一等价定义

参考文献

致谢