关于可平面图的边剖分的若干结果

摘要

本文考虑的图若无特殊声明均为简单、无向有限图。对于一个图G=G(V(G)，E(G))，本文用V(G)和E(G)分别表示图的顶点集合和边集合。对任意的ν∈V(G)，采用d<,G>(ν)表示顶点ν在G中的度数。△(G)和δ(G)分别表示图G的最大度和最小度。对V(G)的子集S，用G-S表示从G中删去顶点集合S及其关联的边所得到的子图。若S={ν}，则令G-ν=G-{ν}。对E(G)的子集x，用G-X表示从G中删去边集合X所得的子图。若X={e}，则G-{e}简记为G-e。若存在V(G)的两个不交子集X、Y，使得V(G)=X ∪Y，且G的所有边均一个端点在X内，另一个端点在Y内，则称G为二部图，记为G=(X，Y，E(G))。 若图G可以表示在平面上，并且任两条边仅在其端点处才可能相交，则称G是可平面图。图G的这种平面上的表示法称为G的一个平面嵌入，或称为平面图。对于一个平面图G，我们用F(G)来表示G的面集合。对于一个面f，我们把将f围起来的所有的边所构成的集合称为f的边界，并且称f关联于其边界上的所有的顶点和边。同样地，可以定义，的度dG(f)为f的边界上的边数。若G的两个面f<,1>和f<,2>有一条公共边e，则称面f<,1>和f<,2>相邻接于边e。若存在映射φ：E(G)→{1，2，…，κ}，对于G中任意两条相邻接的边e<,1>和e<,2>，满足φ(e<,1>)≠φ(e<,2>)，则称G是κ一边可染色的。这时对于任意的1≤i≤κ，φ<'-1>(i)的边导出子图均是图G的一个匹配。我们把使得图G具有κ-边染色的最小正整数κ定义为G的边染色数，记作X(G)。 若图的每一个连通分支都是一条路，则称该图为一个线性森林。我们称映射ψ：E(G)→+{1，2，…，t)为图G的一个t-线性染色，如果对于任意的1≤α≤t都有，ψ<'-1>(α)的边导出子图是一个线性森林。本文把使图G具有t-线性染色的最小正整数t称为G的线性荫度，记作lα(G)。 图的染色理论是图论的一个重要分支，是图论研究中最活跃的课题之一。根据一定的规则将一组目标划分为不同的种类，这是数学中的一个基本方法。不同的规则决定着该组中任意一对目标是否在同一个类中。图的染色理论就是研究这类问题的一门理论，它有着相当广泛的应用背景。各种形式的日程表问题，时间表问题以及排序问题，从根本上来说都可以归结为染色问题。对染色理论的研究最早可以追溯至1852年，即著名的“四色猜想”的提出。而图的边染色问题引起人们关注的时间相对较晚。但是，许多研究领域，如地图染色，匹配理论以及拉丁方，都与边染色问题有着紧密的联系。关于边染色的第一篇文章出现在1880年，由P.G.Tait在对“四色猜想”做进一步的研究时，证明出“任一2-边连通，3-正则的甲面简单图是3-边可染色的”与“四色猜想”足等价的。此后，关于边染色问题的研究又有了一些比较重要的结论，如Konig's Theorem，Shannon's Theorem以及Vizing's Theorem。图的边染色中，根据著名的Vizing's Theprem，可以将简单图分为两类。图的分类问题就是判断一个图G究竟是第一类图，还是第二类图的问题。关于图的分类问题，虽然已有一些相关的结论，但是未解决的部分还有很多。而对于可平面图的边染色的分类问题，Vizing证明出任一△(G)≥8的可平面图G均是第一类图，而△∈{2，3，4，5}的可平面图中存在第二类图。于是Vizing在1968年的时候，提出了著名的可平面图猜想。 图G的线性荫度这一概念是由Harary在1970年提出的。接着在1980年，由Akiyama，Exoo和Harary等人给出了关于正则图的线性荫度的猜想；并且在这一猜想的基础上，产生了著名的线性荫度猜想(the Linear Arboricity Conjecture，简称为LAC)。在对线性荫度猜想进行研究时，J.Wu解决了可平面图条件下这个猜想的大部分情况，只余下△=7这一种情况仍未解决。 本文中主要研究的是可平面图的边染色及线性荫度方面的一些结果。 全文共分三章，第一章简单介绍一下图论中的一些基本概念，并给出边染色、线性荫度问题的历史背景和进展状况以及一些已有的相关结论。这一章是后面其他各章节的基础。 第二章我们主要讨论可平面图的边染色的一些情况。主要结论为：定理2.1.10．设G是最大度为5的可平面图。若G中不含长度为4的圈，或不含长度为5的圈，则G是第一类图。 第三章则讨论了可平面图的线性荫度的一些情况，其主要得出了33个定理。

目录

文摘

英文文摘

论文说明：符号说明

原创性声明及关于学位论文使用授权的声明

第一章引言

§1.1基本概念

§1.2问题产生的背景及其进展情况

§1.3本文的主要结果

第二章可平面图的边染色

§2.1边染色的分类问题

§2.2最大度为5的可平面图的边染色

第三章可平面图的线性荫度

§3.1已有结论

§3.2最大度为7的可平面图的线性荫度

§3.3其它结果

参考文献

致 谢

攻读硕士学位期间发表及完成的论文