| 【中文题名】 | 平面图的性质及图的几种染色研究 |
| 【英文题名】 | Study of the Properties of Planar Graphs and Some Colorings of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-12-28 |
| 【中关键词】 | 平面图,色数,列表染色,m-数,颜色多项式, |
| 【英关键词】 | planar graph,chromatic number,m-number,chromatic polynomial, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 本文主要研究了平面图的低度点个数、在某些情况下的四着色、唯一列表染色。本文还研究了完全二部图和完全r部图的颜色多项式。
首先从度序列的角度出发研究了连通图的性质，证明了一个图是连通图的充要条件是其度序列d=(d_1，d_2，…，d_n)满足：sum from i=1 to n d_i为偶数，sum from i=1 to n d_i≥2(n-1)，且对1≤k≤n成立，sum from i=1 to k d_i≤k(k-1)+sum from i=k+1 to n min{k，d_i}；证明了正整数序列d=(d_1，d_2，…，d_n)是树的度序列的充要条件是sum from i=1 to n d_i=2(n-1)。在此基础上证明了一个平面图在顶点数小于12或每个点的度都小于5的情况下四色猜想都是成立的。
其次，对图的唯一3-列表染色也进行了研究，证明了判断一个图为唯一3-列表可染色图的一个充要条件和一个充分条件，并且找到一类m数为4的平面图。
最后，还对图的染色的方法数进行了研究，利用组合的方法求出了完全二部图以及完全r部图的颜色多项式，并得到了一个组合数的公式... |
| 【论文题纲】 |
|
第一章 绪论 |
8-11 |
|
第二章 图的基本知识 |
11-15 |
|
第三章 平面图的某些性质 |
15-24 |
|
3.1 连通图的度序列及连通平面图的低度点个数 |
15-21 |
|
3.2 平面图的点染色 |
21-24 |
|
第四章 唯一列表染色 |
24-28 |
|
4.1 列表染色的相关概念 |
24-25 |
|
4.2 唯一3列表可染色图 |
25-28 |
|
第五章 二部图的颜色多项式 |
28-33 |
|
5.1 背景介绍及基本概念 |
28-30 |
|
5.2 二部图的颜色多项式 |
30-33 |
|
结束语 |
33-35 |
|
致谢 |
35-36 |
|
参考文献 |
36-39 |
|
详细摘要 |
39-53 |
|
| 【DOI】 | LunWen.ID:2.2008.11771 |
