超图的边着色

作     者：王娜 

作者单位：新疆师范大学 

学位级别：硕士

导师姓名：王迪吉;杜智华

授予年度：2008年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：边着色 完全r-partitioned超图 线性超图 线性超树 成分着色 

摘      要：超图是一般图的重要推广,超图的着色概念也是一般图着色概念的自然推广。对于超图的着色有很多各种各样的应用背景,如时间表问题,资源的分配问题。而且它与其它的组合问题也有着广泛的联系,例如极值理论,Ramsey理论,概率方法,差值理论等等。在近三十年中,超图的着色问题已经有许多人研究,并且获得了很多结果。 第一章主要研究完全r-partitioned超图的边着色。设H是一个超图,它的顶点集合V被划分为r个部分即V={V,…,V),给定一个r维向量M=(p,p,…,p)(P∈N,1≤i≤r),H中的边集是V中的每个多重集E并且满足: M (|E∩V|,(|E∩V|,…,(|E∩V|),则我们称H是完全r-partitioned超图K,或记为K。本人在这一章里得到了四个主要结论和一个猜想。 定理1.2.1:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果2|n,则(q(H)-(n-1)(?)…(?),否则(q(H)-n(?)···(?)。 定理1.2.2:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果有t|n,或者(?)|(?)(1≤i≤r),则q(H)=((?))((?))…((?))(?)。 定理1.2.3:若完全r-partitioned超图K,并且设n≤n≤…≤n。如果t(?)n且(?)(?)((?))(1≤i≤r),则 定理1.2.4:若完全r-partitioned超图K,并且设n≤n≤…≤n。则(?) 猜想1.2.1:若完全r-partitioned超图K,并且设n≤n≤…≤n。则(?) 第二章研究了线性超图的边着色。设H是一个超图,如果对任意两条边E,E(i≠j),有|E∩E|≤1。若H是无圈的线性超图则我们称为线性超树。本人在这一章里得到了四个结论。 定理2.2.1:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△-2,q(S)-3,则q(H)≤n。 定理2.2.2:设H是n个顶点上的无环线性超图,若S是由边秩大于等于3的边导出的部分超图。如果△≤3,q(S)≤3,则q(H)≤n。 定理2.2.3:设H为r阶射影平面,则q(H)=r-r+1。 定理2.3.1:设H是线性超树,且H的最大度为△,则q(H)=△。 第三章研究了路,0图,T(见图3.1)这三类图的成分着色。设H是个超图,对于它的一个k-边着色c:E(H)→{1,2,…,k),f(H,c)是由这k种颜色中同一色类导出的子超图中所含分枝数最少的子超图的分枝数。f(H)表示H中所有k-边着色中f(H,c)的最大值,本人在这一章里得到了三个结论。 定理3.2.1:设P是n个顶点的一条路,则f(P)=(?)。 定理3.2.2:f(T)=(?)+1,(见图1(a))。 定理3.2.3:设G是0-图,则f(G) 2,(见图1(b))。