双外平面图的染色问题

论文摘要

图的染色问题,是图论的主要研究问题之一。图的染色一般分为边染色、点染色、点边染色以及其它特定染色。本文研究了双外平面图的两种基本染色问题,证明了四个主要的结论。 以下所说的图G=（V,E）均为有限、无向和简单的,且用V（G）,E（G）分别表示其顶点集合和边的集合,图G的顶点数（或阶）和边数分别用符号ν（G）和ε（G）表示,在图论符号中我们常略去字母G分别用V,E,ν和ε代替V（G）,E（G）,ν（G）,ε（G）。顶点ν的度,记为d（ν）。分别用δ（G）和Δ（G）表示G中顶点的最小度和最大度。N（ν）表示点ν在G中的邻域。G[V′]表示图G的由顶点子集V′导出的子图,G（E）表示G的出边子集E′导出的子图。W（e）表示边e的权。Cn表示圈长。σ（y）表示在σ—染色法下,元素y∈V（G）∪E（G）所染的颜色。Eσ（u）表示在σ—染色法下与点u相关联的边所染颜色的集合。X′（G）表示图G的边色数。XT（G）表示图G全色数。文中所用术语和符号基本与文献[1]中一致。 全文共分为四章,第一章介绍了图论的基本概念和关于图的边染色、全染色的历史、发展状况和已经得到的一些结果。在第一节中,介绍了—些常用的图论术语及相关的概念。第二节介绍了平面图、外平面图的概念。如:定义1.2.1 如果一个图是可嵌入平面的,且它所有顶点出现在无穷面的边界上,称为外平面图.无穷面称为外面,用f0表示;其余面称为内面。在外面周界上的边称为外边,其余的边称为内边。 在外平面图的基础上,我们定义一种新的类型的图即双外平面图,它是外平面图的一种推广。 定义1.2.2 所有点出现在两个面的边界上的平面图,称为双外平面图。我们把这两

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 前言
• 1.1 基本概念
• 1.2 平面图
• 1.3 染色
• 1.4 本论文的主要结果
• 第二章 双外平面图的结构及其性质
• 2.1 双外平面图的结构
• 2.2 双外平面图的性质
• 第三章 主要结果及其证明
• 3.1 双外平面图的边染色
• 3.2 双外平面图的全染色
• 第四章 可以继续探讨的问题
• 参考文献
• 致谢
• 攻读学位期间发表的论文
• 学位论文评阅及答辩情况表