| 【中文题名】 | 特殊平面图的全染色 |
| 【英文题名】 | The Total Coloring of Particular Planar Graphs |
| 【学科专业】 | 远筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-4-12 |
| 【中关键词】 | 平面图,全染色,全染色数,圈,, |
| 【英关键词】 | planar graph,total coloring,total chromatic number,cycle, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 本文考虑的图如无特别申明均为简单无向有限图。对于一个图G=G(V(G)，E(G)，ψ_G)，我们用V(G)≠φ和E(G)表示图的顶点集合和边集合，ψ_G是联系着G中的边和一对无序顶点之间的关联函数。一个图G，如果可以将它画在平面上，使它的边仅在端点上才能相交，则称图G为可嵌入平面的，或称为平面图。平面图G的这种平面上的画法称为图G的一个平面嵌入，平面图的平面嵌入称为平图。一个平图G把平面划分成若干个连通区域，这些区域的闭包称为G的面。
对于ν∈V(G)，我们用d_G(ν)表示顶点ν在G中的度数，简记为d(ν)，Δ(G)和δ(G)分别表示G的最大度和最小度，不会混淆时，也用Δ和δ表示G的最大度和最小度。G中的途径是一个有限非空的顶点和边的交错序列。如果顶点两两不相同，则称为路。起点和终点相同的路称为闭路，闭路又称为圈。长为k的圈称为k-圈。一个面所关联的边的个数(割边要计算两次)，被称为面的度，用r(f)表示。给定一个图G，G的全k染色(全k可染)是指至多用k种颜色，对G的顶点和边同时进行染色，使得相邻的两个元素(点和点，点和边，边和边三种情况)不染同一种颜色。G的全染色数x_T(G)是指G的全... |
| 【论文题纲】 |
|
中文摘要 |
4-7 |
|
英文摘要 |
7-10 |
|
第一章 引言 |
10-16 |
|
1.1 基本概念 |
10-11 |
|
1.2 图的全染色综述及本文的主要结果 |
11-13 |
|
1.3 本文所用的符号和基本引理 |
13-16 |
|
第二章 3-圈不重边的平面图 |
16-25 |
|
2.1 3-圈不重边平面图的全染色猜想 |
16-19 |
|
2.2 Δ(G)≥9时的全染色 |
19-21 |
|
2.3 不含5-圈的全染色 |
21-25 |
|
第三章 3-圈不重点的平面图 |
25-31 |
|
3.1 Δ(G)≥8时的全染色 |
25-27 |
|
3.2 不含4-圈的全染色 |
27-31 |
|
第四章 其余扩充结果 |
31-38 |
|
4.1 每点至多关联2个3-面平面图的全染色猜想 |
31-34 |
|
4.2 Δ(G)≥8且每点至多关联2个3-面平面图的全染色 |
34-35 |
|
4.3 对Δ(G)≥9且每点至多关联(?)Δ(G)/2(?)个3-面平面图的全染色 |
35-38 |
|
参考文献 |
38-41 |
|
致谢 |
41-42 |
|
学位论文评阅及答辩情况表 |
42 |
|
| 【DOI】 | LunWen.ID:2.2008.11790 |
