| 【中文题名】 | 无四圈环面图的4-选色问题 |
| 【英文题名】 | 4-Choosability of Toroidal Graphs Without 4-Cycles |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-10 |
| 【中关键词】 | 4-圈,环面图,列表染色,4-可选色,, |
| 【英关键词】 | 4-cycles,toroidal graph,list coloring,4-choosable, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
对图G的每个顶点v，令L(v)表示可用于点v的颜色列表，则给定图G的顶点上的一个颜色列表集合L={L(v)|v∈V(G)}。一个列表染色是一个真染色f，它使得f(v)∈L(v)对所有v均成立。如果对所有顶点v，只要|L(v)|≥k，均存在一个列表染色，则称图G是k—可选色的或简称为k-可选的，并记列表色数、选择数或可选数χl(G)=min{k|图G是k—可选色的}。
没有边缘而且可以剖分成有限个多边形的曲面称为闭曲面。球面是最简单的闭曲面。在球面上添加一些手柄得到了新的表面，其亏格是所添加的手柄的个数。我们将亏格为γ的表面记为S_γ。图G的亏格是使得G能够嵌入到S_γ上的最小γ值，使得它的边仅在顶点相交。亏格是0、1的图分别称为平面图、环面图。
在文献[18]中，作者证明了无4—圈的平面图是4—可选的，本文在此基础上证明：
定理：无4—圈的环面图是4—可选的。 |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-6 |
|
前言 |
6-8 |
|
第一章 基本概念及已有结论 |
8-12 |
|
1.1 图论基本概念与符号 |
8-9 |
|
1.2 图的染色定义 |
9 |
|
1.3 图的列表染色定义 |
9-10 |
|
1.4 与本文有关的一些已知结果 |
10-11 |
|
1.5 本文的主要结果 |
11-12 |
|
第二章 定理证明 |
12-34 |
|
2.1 可约构形 |
12-16 |
|
2.2 权传递规则 |
16-17 |
|
2.3 点,面的新权重计算及引理2.1证明 |
17-32 |
|
2.4 结论证明 |
32-34 |
|
第三章 可以进一步研究的问题 |
34-35 |
|
参考文献 |
35-39 |
|
致谢 |
39 |
|
| 【DOI】 | LunWen.ID:2.2008.11849 |
