| 【中文题名】 | 平面图的边染色 |
| 【英文题名】 | Edge Coloring of Planar Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-3-28 |
| 【中关键词】 | 平面图,边色数,边选择数,最大度,, |
| 【英关键词】 | planar graph,chromatic index,list-chromatic index,maximum degree, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 用G=(V，E)表示一个顶点集为V，边集为E的有限、简单无向图，{1，2，…，k}表示k个颜色的集合。G的一个正常k-边染色是一个映射φ：E→{1，2…，k}使得相邻的边接受不同的色。如果G有一个正常k-边染色，则称G是k-边可染的。G的边色数x~1(G)是使得G是正常k-边可染的最小的非负整数k。
图G的一个边色列表是一个颜色集合簇L，它指定G的每条边e一个颜色集合L(e)。若G有一个正常的边染色φ，使得对每一条边e∈E，φ(e)∈L(e)，则称G为L-边可染的。若对每一个满足|L(e)|=k，e∈E的L，G都是L-边可染的，则称G是k-边可选择的。G的边列表色数，或边选择数x′_l(G)是使得G是k-边可选择的最小的非负整数k。
关于图的边染色问题，Vizing在1964年证明了下述著名定理：Δ(G)≤x′(G)≤Δ(G)+1，其中，Δ(G)为G的最大度。由此定理可引出简单图的分类问题。称x′(G)=Δ(G)的简单图G为第一类的，否则，称为第二类的。
本文在前人的工作基础上继续研究平面图的分类问题，证明了：
(1) 最大度为6且不含有7-圈的... |
| 【论文题纲】 |
|
摘要 |
2-3 |
|
ABSTRACT |
3-5 |
|
目录 |
5-6 |
|
一、绪论 |
6-11 |
|
(一) 基本概念 |
6-7 |
|
(二) 边染色问题的研究概况与本文的研究工作 |
7-11 |
|
二、最大度为6的平面图的分类 |
11-24 |
|
三、最大度为5的平面图的分类 |
24-30 |
|
四、最大度为4的平面图的分类 |
30-33 |
|
五、平面图的边选择数 |
33-39 |
|
参考文献 |
39-42 |
|
致谢 |
42-43 |
|
在学期间的研究成果及发表的论文 |
43-45 |
|
| 【DOI】 | LunWen.ID:2.2008.11757 |
