论文部分内容阅读
本文考虑的图均为简单无向有限连通图.一个图G,若能被画在平面上,使得其每两条边仅在端点处才能相交,则称它为可嵌入平面的,简称可平面的.平面图的这种在平面上的画法称为一个平面嵌入,也称之为是一个平面图.一个平面图G把平面划分成若干个连通区域,这些区域的闭包称为G的面,其中唯一的一个无界面称为G的外部面,其它的面均为内部面.对于一个平面图G,我们用V(G)、E(G)和F(G)分别表示图的顶点集合、边集合和面集合,两个面f1,f2∈F(G),当且仅当f1和f2有公共边时称它们为相邻;面的边界上的点和边称为与该面相关联,与面f相关联的边的数目称为面f在G中的度(割边计算两次),记为dG(f).G中的面度最大者称为G的最大面度,记为FM(G);外部面的面度记为Fext(G),同时,用Δ(G)、δ(G)分别表示G的顶点的最大度和最小度.
平面图G的有点面约束的边染色,也称双约束边染色,是指对G的边进行染色使得关联同一点的边有不同的颜色且在同一面上的边也有不同的颜色:使图G可进行双约束边染色所需的最小颜色数称为G的双约束边色数,记为χe/vf(G).O.V.Borodin和D.R.Woodall首先提出了双约束边染色的概念,并针对外平面图的双约束边色数进行了研究,得出了比较好的结果.本文针对平面图的双约束边染色问题进行了进一步的广泛研究,其中重点就若干特殊类型的平面图,如近似Halin图、近似外平面图、双外平面图、高度平面图等,展开了较深入的讨论.平面图G,如果δ(G)≥3且G去掉外部面的边界之后是一棵树,就称为是一个Hailin图;而一个非Hailin图如果近去掉或者是收缩一条边以后就成为一个Hailin图,我们称为是一个近似Hailin图.平面图G,如果其所有的顶点都在同一个无界面的边界上,则称它为一个外平面图;一个非外平面图如果近去掉或者是收缩一条边以后就成为一个外平面图,我们也称为是一个近似外平面图.所有顶点都出现在两个面上的平面图称为双外平面图.平面图G,若满足Δ(G)=|V(G)|-k,k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图,无割点的hk-图又称为pk-图.
全文共分五章,第一章介绍了图论中的若干基本概念,简单综述了图的染色理论的发展过程以及与本文相关的一些已有的结果.第二章首先介绍了Halin图的双约束边染色已经的较好的结果.然后分别研究了两类近似Hailin图(几乎Halin图,Halin图的弱剖分图)的双约束边染色问题.第三章介绍了关于外平面图的双约束边染色的已有结果,重点就两类近似外平面图(几乎外平面图,外平面图的弱剖分图)的双约束边染色问题展开了研究.第四章介绍了双外平面图的特点,研究了特殊的双外平面图的双约束边染色问题.第五章初步研究了特殊的高度平面图的双约束边染色问题.得出的主要结论有:定理1设G是几乎Halin图,且余边e位于G-e的内部面上,则有χe/vf(G)=Fext(G).定理2设G是几乎Halin图,且余边e位于G-e的外部面上,如果G-e非轮图,且存在有内部面达到了最大面度,则有χe/vf(G)=FM(G).定理3设G是Halin图的弱剖分图,则有χe/vf(G)=FM(G).定理4如果G是带有余边e的几乎外平面图,而G-e恰是由一个圈加上一条对角线构成的外平面图,那么FM(G)≤χe/vf(G)≤FM(G)+1.定理5如果G是带有余边e的几乎外平面图,而G-e是Δ=4的2-连通极大外平面图,那么χe/vf(G)≤max{FM(G)+1,Δ(G)+1}.定理6若G恰好是Cn加上一条k-对角路构成(n≥3,k≥1),则χe/vf(G)=n+k≤3/2FM(G),且当且仅当n=2k且对角路为正对角路时,达到最大值3/2FM(G).定理7假设G为2-连通的外平面图,G为G的弱剖分图,只要G不是由一个圈加上一条对角路,就有χe/vf(G)=Fext(G).定理82-连通图G如果是正则双外平面图,那么χe/vf(G)≤FM(G)+1.定理9设G是|V(G)|≥6的p1类图,则必有χe/vf(G)≤Δ(G)+1,且χe/vf(G)=Δ(G)+1当且仅当图G同构于图5.1.1所示的图PΔ.
在本文的最后,提出了一些问题以及有关平面图的双约束边色数的猜想,以待进一步研究.