| 【中文题名】 | 圆色数和圆不完美图 |
| 【英文题名】 | Circular Chromatic Number and Circular Imperfect Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-11-14 |
| 【中关键词】 | 圆色数,圆团数,圆完美,圆不完美,边临界,G_k~d图 |
| 【英关键词】 | circular chromatic number,circular clique number,circular perfect graph,circular imperfect graph,edge-critical graph,G_k~d graph,core,Hajos construction,minimully circular imperfect,homomorphism, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 一个图G的圆色数x_c(G)是图G的色数x(G)的自然推广,最初是由Vince于1988年以“星色数”的定义提出来的。朱绪鼎在文献[3]中用类似Hajos定理的一些操作,利用G_k~d的复制,构造了所有圆色数至少是k/d的图,k/d≥3。本文利用此文献中的三种操作构造了圆色数相等的一类图,计算出结果图S_1,S_2,S_3[3]的圆团数,在此基础上给出S_1,S_2,S_3[3]为圆不完美的充分条件,同时给出如下定理[3]的简化证明:如果r≥3,G_1,G_2,…G_7是圆色数至少为r的图,则x_c(S_3)≥r。文章的最后给出了圆色数的另一等价定义:任意图G,x_c(G)=min{k/d|2d≤k≤|V(D)|且ξ_(k,d)(G)≤k/d}。(其中D是G的定向图) |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-6 |
|
第一章 绪论 |
6-8 |
|
第二章 前言 |
8-15 |
|
§2．1 基本概念 |
8-9 |
|
§2．2 图的圆色数 |
9-11 |
|
§2．3 已有的相关结论 |
11-15 |
|
第三章 G_k~d图，Hajós构造 |
15-21 |
|
§3．1 G_k~d图的定义和性质 |
15-17 |
|
§3．2 Hajós构造 |
17-21 |
|
第四章 本文的主要结果 |
21-31 |
|
§4．1 构造一类圆色数相等的图 |
21-23 |
|
§4．2 圆不完美图 |
23-29 |
|
§4．3 圆色数的另一等价定义 |
29-31 |
|
参考文献 |
31-34 |
|
致谢 |
34 |
|
| 【DOI】 | LunWen.ID:2.2008.11583 |
