图的区间边着色的收缩图方法

摘要

图论作为数学的一个分支,近年来得到了较快发展和广泛应用,已广泛应用于运筹学,控制论,信息论和计算机科学等各个领域.
　　一般说来,图的着色问题最早起源于著名的”四色问题”.由于图的着色问题反映了广泛而深刻的实际背景,它的研究带动了整个图论的发展.如今图着色理论被广泛应用于化学品的贮藏,考试日程和安排会议等许多实际问题上.
　　图G的一个用了颜色1,2,...,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作N.对图G∈N,使得G有一个区间t-着色的t的最小值和最大值分别记作w(G)和W(G).本文中,我们给出了图的区间着色的收缩图方法.利用此方法我们对双圈图G∈N,证明了w(G)=Δ(G)或Δ(G)+1,并且完全确定了w(G)=Δ(G)及w(G)=Δ(G)+1的双圈图类.
　　全文共分为三章.第一章首先介绍了图着色的研究背景及相关应用,以及图的区间边着色的刻画问题;其次介绍了基本概念及术语;最后列出了图的区间边着色研究的一些已有结果.第二章给出了收缩图方法.第三章主要利用前面的方法给出了双圈图区间边着色的下界.第三章分为三个小节.第一节中给出了双圈图G∈B∞的区间边着色的下界w(G);第二节中给出了双圈图G∈Bθ的区间边着色的下界w(G);第三节中给出了双圈图G∈B??的区间着色的下界w(G).

目录

第一章 引言

1.1 研究背景

1.2 基本概念及术语

1.3 图的区间边着色刻画的已有成果

第二章 收缩图方法

第三章 双圈图的区间边着色的下界w(G)

3.1 双圈图G∈B∞ 的区间边着色的下界w(G)

3.2 双圈图G∈Bθ 的区间边着色的下界w(G)

3.3 双圈图G∈B∞的区间边着色的下界w(G)

参考文献

硕士期间发表论文清单

致谢