图的染色问题，是图论的主要研究问题之一.图的染色一般分为边染色、点染色、点边染色以及其它特定染色.本文研究了双外平面图的两种基本染色问题，证明了四个主要的结论. 以下所说的图G=(V，E)均为有限、无向和简单的，且用V(G)，E(G)分别表示其顶点集合和边的集合，图G的顶点数(或阶)和边数分别用符号v(G)和ε(G)表示，在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G)，E(G)，v(G)，ε(G).顶点v的度，记为d(v).分别用δ(G)和△G)表示G中顶点的最小度和最大度.N(v)表示点(p)在G中的邻域G[V′]表示图G的由顶点子集V′导出的子图，G(E)表示G的由边子集E′导出的子图.w(e)表示边e的权.Cn表示圈长.σ(y)表示在σ-染色法下，元素y∈V(G)(∪)E(G)所染的颜色.Eσ(u)表示在σ-染色法下与点u相关联的边所染颜色的集合.x(1)(G)表示图G的边色数.X(T)(G)表示图G全色数.文中所用术语和符号基本与文献[1]中一致. 全文共分为四章，第一章介绍了图论的基本概念和关于图的边染色、全染色的历史、发展状况和已经得到的一些结果.在第一节中，介绍了一些常用的图论术语及相关的概念.第二节介绍了平面图、外平面图的概念.如： 定义1.2.1如果一个图是可嵌入平面的，且它所有顶点出现在无穷面的边界上，称为外平面图.无穷面称为外面，用f0表示；其余面称为内面.在外面周界上的边称为外边，其余的边称为内边. 在外平面图的基础上，我们定义一种新的类型的图即双外平面图，它是外平面图的一种推广. 定义1.2.2所有点出现在两个面的边界上的平面图，称为双外平面图.我们把这两个面称为外面，记为F0={f0，f1}，其余的面称为内面，用FF0来表示. 在第一章第三节中，介绍了图的边染色、全染色的概念及有关猜想，发展状况，和已经得到的一些结果. 定义1.3.1对于图G=(V，E)，使得V(或E)中任何两个相邻元素均染不同颜色的方法，称为G的正常的点(或边)染色；使得V(∪)E中任何两个相邻和相关联的元素间均染不同颜色的方法，称为G的正常全染色. 定义1.3.2使得G为正常点(边、全)染色的最少颜色数，称为G的点(边、全)色数，简记做χ(G)(χ′(G)，χ(T)(G)). 为了更好地描述外平面图和双外平面图的结构性质，在第二章第一节我们给出如下有关定义.记V(f)，E(f)分别为与f相关联的顶点和边的集合. 定义2.1.1：平面图的边面对偶GEF，其中V(GEF)=E(G)∪F(G)；E(GEF)={(e，f)：e∈E(G)，f∈F(G)且e与f在G中相关联} 从定义2.1.1可以看出一个事实：平面图G的边面对偶GEF就是它的对偶图G*的每条边经过一次剖分后所得到的图.针对外平面图和双外平面图，我们可以给出一些相对比较弱一些的对偶定义. 定义2.1.2：设G为一个外平面图，若对于G中的每一个内面f都有GWF的一个顶点与之对应，GWF的两个顶点相邻当且仅当的G两个内面相邻，则称GWF是外平面图的弱对偶图. 陈东灵，吴建良等在文献[3]中定义了外平面图的弱对偶图，并证明了外平面图的弱对偶图的结构. 以同样的方法可以定义双外平面图的弱对偶图和边面弱对偶图. 定义2.1.3：设为G一个双外平面图，若对于G中的每一个内面都有GWF的顶点与之对应，GWF的两个顶点相邻当且仅当的G两个内面相邻，则称GWF是双外平面图的弱对偶图. 定义2.1.4：外平面图的边面弱对偶GWEF=GEFfo，其中：fo对应于G的唯一无穷外面；双外平面图G的边面弱对偶GWEF=GEF{f0，f1}.其中：f0，f1对应于G中所规定的两个外面. 在第二章第一节中，证明了双外平面图的弱对偶图的结构，得到性质1：双外平面图G的弱对偶和边面弱对偶都是至多包含一个圈的图. 在第二章第二节中，证明了双外平面图的性质定理，得到性质2：设G是△(G)≥6的2连通的双外平面图，则G至少有下列情况之一出现： (1)存在一条边e=uv，满足d(u)+d(v)≤7，即存在一条边的权w(e)≤△(G)+1；或者(2)存在一个偶圈V1V2…V2nV1使得d(V1)=d(V3)=…d(V2n-1)=2即存在一个2-交错圈. 在第三章中，我们证明了双外平面图的边染色的定理，以及双外平面图的全染色定理. 定理1：：若G是△(G)≥6的2连通的双外平面图，则χ′(G)=△(G). 定理2：对△(G)≥6的2连通的双外平面图G，有χ(T)(G)=△(G)+1. 在第四章中，我们提出了可进一步研究的几个问题.