超图的边着色

论文摘要

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

论文目录

• 中文摘要
• Abstract
• 文献综述
• 1.完全r-partitioned超图
• 1.1 基本概念
• 1.2 主要结论
• 2.线性超图
• 2.1 研究背景
• 2.2 一般线性超图
• 2.3 线性超树
• 3.特殊图的成分着色
• 3.1 研究背景
• 3.2 主要结论
• 参考文献
• 致谢