论文部分内容阅读
一个图G=(V(G),E(G))的边染色是指从其边集合E(G)到自然数子集{1,2,…,r}上的一个满射C。如果图G有这样的一个染色C,我们就称图G是一个边染色图,或r-边染色图,并用C(e)来表示边e的颜色。给定图G中的一个顶点ν,顶点ν的色邻域CN(ν)是指集合{C(e):e与ν关联}。顶点ν的色度记为dc(ν)=|CN(ν)|。一棵树被称为单色的是指这棵树中的所有边上所染颜色都相同。
1991年,Erdos,Gyarfas和Pyber提出了边染色图的单色树划分数的概念。r-边染色图G的单色树划分数,或简称为树划分数,记作tr(G),是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个顶点不交的单色树覆盖。Erdos,Gyarfas和Pyber猜想r-边染色完全图的单色树划分数是r-1,其中r≥2,并且他们证明了r=3时猜想的正确性。猜想对于r=2的情况等价于Erdos和Rado的断言:对任意的图G,图G和图G的补图至少有一个连通。对于无限完全图,Hajnal等人证明了一个r-边染色无限完全图的单色树划分数至多是r。对于有限完全图,Haxell和Kohayakawa证明了当n≥3r4r!(1-1/r)3(1-r)logr,任意r-边染色完全图Kn含有至多r个两两不同色的单色树,并且他们的顶点集合划分了Kn的顶点集合。Haxell和Kohayakawa还证明了当n充分大时,r-边染色的完全二部图Kn,n的单色树划分数至多是2r。一般地,确定tr(G)的精确的值是很困难的。
与单色树划分数相关的一个问题是r-边染色图G的单色树覆盖数,或简称为树覆盖数,它是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个单色树(可以相交)覆盖。对于完全图,以某个点为中心的所有单色星构成了一个覆盖,所以r-边染色完全图的单色树覆盖数至多是r。Erdos,Gyarfas和pyber关于树划分数的猜想的一个弱形式是:r-边染色完全图的单色树覆盖数是r-1。
本文分为三部分,第一部分主要研究了2-边染色完全二部图的单色树划分问题,第二部分主要研究了3-边染色完全等部二部图的单色树划分问题,第三部分主要研究了2-边染色和3-边染色完全二部图的单色树覆盖问题。
第二章中我们研究了2-边染色完全二部图的单色树划分。对于2-边染色的完全多部图K(n1,n2,…,nk),Kaneko,Kano和Suzuki证明了:设n1,n2,…,nk(2≤k)是满足1≤n1≤n2≤…≤nk的整数,并且n=n1+n2+…+nk-1,m=nk,则t2(K(n1,n2,…,nk))=[m-2/2n]+2。特别地,t2(Km,n)=[m-2/2n]+2,其中1≤n≤m。金泽民等人在2006年给出了2-边染色的完全多部图的单色树划分的多项式时间算法。第二章中我们给出了2-边染色的完全二部图的单色树划分更精细的刻画,我们将2-边染色完全二部图分为几种结构,并给出每种结构的单色树划分数。我们得到如下结果。
1.如果K(A,B)是一个2-边染色完全二部图,则它是下面四种结构中的一种:(1)K(A,B)有单色支撑树,(2)K(A,B})∈M,(3)K(A,B)∈S2,(4)K(A,B)∈S1。
2.如果K(A,B)∈M,则K(A,B)的顶点集可被两个同色的单色树覆盖;如果K(A,B)∈S2,则K(A,B)的顶点集要么被一个孤立点和一个单色树覆盖,要么被两个不同色的顶点不交的单色树覆盖;如果K(A,B)∈S1,并且m=|A|>|B|=n,则K(A,B)的顶点集可被至多[m-2/2n]+2个顶点不交的单色树覆盖,并且存在边染色使K(A,B)的顶点集恰被[m-2/2n]+2个顶点不交的单色树覆盖。
第三章中我们研究了3-边染色等部完全二部图的单色树划分。我们给出了几种色度条件下的单色树划分数。设K(A,B)是一个3-边染色等部完全二部图,我们得到如下结果。
1.如果存在色度为1的顶点,则t3(K(A,B))=3。
2.如果每个顶点的色度都是2,则t3(K(A,B))=2。
3.如果每个顶点的色度都是3,则t3(K(A,B))=3。
4.如果每个顶点的色度都至少是2,并且恰有一个部有色度为3的顶点,则亡3(K(A,B))=4。
第四章中我们研究了2-边染色和3-边染色完全二部图的单色树覆盖。我们的到了如下结果:
1.2-边染色完全二部图的单色树覆盖数是2。
2.3-边染色完全二部图的单色树覆盖数是4。