| 【中文题名】 | 若干图类的全染色、完备染色和选色问题研究 |
| 【英文题名】 | On the Total Coloring、Entire Coloring and Choosability Coloring of Some Graphs |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-6-4 |
| 【中关键词】 | 平面规则网格,全染色,全色数,列表染色,选色, |
| 【英关键词】 | regular planar meshes,total coloring,total chromatic number,list coloring,choosable coloring, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 染色问题是图论的重要问题之一。它起源于四色问题的研究。有很强的理论意义和实际意义。目前，随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域之一。是图论研究中一个很活跃的课题，各类染色问题被相继提出并加以发展、应用。
本文主要研究平面规则网格——方形网格(square mesh)、六角网格(hexagonal mesh)和蜂巢网格(honeycomb mesh)的全染色问题和完备染色问题以及不含4-圈、5圈及相邻3-圈且非3-可选的平面图的选色问题。
首先，根据平面规则网格的结构特性，构造性地给出了方形网格、六角网格和蜂巢网格的全染色方案和完备染色方案，并根据所给出的全染色方案，提出了解决这三种平面规则网格全染色问题的全染色算法，这三种算法可以在多项式时间内完成对这三种平面规则网格的全染色，时间复杂度为O(n~2)：证明了这三种平面规则网格的全色数为其最大顶点度数加1；方形网格、六角网格的完备色数为其最大顶点度数加3；蜂巢网格的完备色数为其最大顶点度数加4，染色方案是最优的。
其次，对于Montassier等人给出的不含4-圈、5圈及相邻3-圈且非3-... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-10 |
|
第1章 绪论 |
10-14 |
|
1.1 引言 |
10-11 |
|
1.2 全染色问题的发展及现状 |
11-12 |
|
1.3 完备染色问题的发展及现状 |
12 |
|
1.4 选色问题的发展及现状 |
12-13 |
|
1.5 本文的研究内容与安排 |
13-14 |
|
第2章 基本概念及预备知识 |
14-20 |
|
2.1 基本概念与记号 |
14-15 |
|
2.2 几种典型的图染色 |
15-16 |
|
2.3 全染色的主要结论 |
16-18 |
|
2.4 完备染色的主要结论 |
18-20 |
|
第3章 网格的全染色及完备染色 |
20-48 |
|
3.1 平面网格的坐标系 |
20-22 |
|
3.1.1 方形网格的坐标系 |
20-21 |
|
3.1.2 六角网格的坐标系 |
21 |
|
3.1.3 蜂巢网格的坐标系 |
21-22 |
|
3.2 平面网格的全染色方案 |
22-28 |
|
3.2.1 方形网格的全染色方案 |
22-25 |
|
3.2.2 六角网格的全染色方案 |
25-26 |
|
3.2.3 蜂巢网格的全染色方案 |
26-28 |
|
3.3 平面网格的全染色算法 |
28-40 |
|
3.3.1 方形网格的全染色算法 |
28-32 |
|
3.3.2 六角网格的全染色算法 |
32-34 |
|
3.3.3 蜂巢网格的全染色算法 |
34-40 |
|
3.4 平面网格的完备染色方案 |
40-48 |
|
3.4.1 方形网格的完备染色方案 |
40-44 |
|
3.4.2 六角网格的完备染色方案 |
44-46 |
|
3.4.3 蜂巢网格的完备染色方案 |
46-48 |
|
第4章 更小的不含4-圈、5圈及相邻3-圈的非3-可选图 |
48-53 |
|
4.1 定义及相关结果 |
48-49 |
|
4.2 不含4圈、5-圈和相交3-圈的平面图 |
49-53 |
|
第5章 结束语 |
53-54 |
|
5.1 本文研究的主要工作 |
53 |
|
5.2 待研究的问题 |
53-54 |
|
参考文献 |
54-58 |
|
攻读学位期间公开发表论文 |
58-59 |
|
致谢 |
59-60 |
|
研究生履历 |
60 |
|
| 【DOI】 | LunWen.ID:2.2008.11807 |
