论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图。对于一个图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-边可染色的”与“四色猜想”足等价的。此后,关于边染色问题的研究又有了一些比较重要的结论,如Konigs Theorem,Shannons Theorem以及Vizings Theorem。图的边染色中,根据著名的Vizings 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个定理。