| 【中文题名】 | 不含相邻三角形平面图的4-选色问题 |
| 【英文题名】 | The 4-choosability of Some Plane Graphs without Adjacent Triangles |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2004-10-19 |
| 【中关键词】 | 选色,平面图,三角形,,, |
| 【英关键词】 | choosable,plane graph,triangle., |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 设k为正整数，G为图。我们给G每点一个长为k的任意表，如果存在一个点着色，使得每个点都可从表中得到一种颜色，则称G为k-可选色的。本文中证明了一些不含相邻三角形的平面图是4-可选色的。
(1)不含相邻三角形，并且四面和三面不相邻的平面图是4-可选色的。
(2)不含相邻三角形，并且四面的距离至少为3的平面图是4-可选色的。
由于直接证明(1)(2)有困难，本文中给出了两个重要引理，由这两个引理完成了本文的证明。
(3)不含相邻三角形，四面和三面不相邻，并且δ≥4的平面图至少含有满足下列条件之一的圈或子图：
(ⅰ)每点都为4度点的4-圈。
(ⅱ)每点都为4度点，并且恰含有一弦u_1u-3的6-圈u_1u_2…u_5u_1。
(ⅲ)(?)-子图。
(4)不含相邻三角形，四面的距离至少为3，并且δ≥4的平面图至少含有满足下列条件之一的圈或子图： |
| 【论文题纲】 |
|
Abstract |
5-7 |
|
摘要 |
7-9 |
|
1 Introduction |
9-11 |
|
1.1 Basic definitions and notations |
9-10 |
|
1.2 Some sufficient conditions of 4-choosable |
10-11 |
|
2 Structure of some plane graphs |
11-28 |
|
2.1 Theorem 2.1 |
11-16 |
|
2.2 Theorem 2.2 |
16-28 |
|
3 Application to choosability |
28-36 |
|
3.1 Given some lemmas |
28-34 |
|
3.2 Theorem 3.13 and Theorem 3.14 |
34-36 |
|
4 Reference |
36-37 |
|
| 【DOI】 | LunWen.ID:2.2008.11467 |
