完全二部图的单色树划分和单色树覆盖

【作者】 刘凤霞；

【导师】 李学良；

【作者基本信息】 南开大学 ， 应用数学， 2009， 博士

【摘要】 一个图G=（V（G）,E（G））的边染色是指从其边集合E（G）到自然数子集{1,2,…,r}上的一个满射C。如果图G有这样的一个染色C,我们就称图G是一个边染色图,或r-边染色图,并用C（e）来表示边e的颜色。给定图G中的一个顶点v,顶点v的色邻域CN（v）是指集合{G（e）:e与v关联}。顶点v的色度记为d^c（v）=|CN（v）|。一棵树被称为单色的是指这棵树中的所有边上所染颜色都相同。1991年,Erd（o|¨）s,Gyarfas和Pyber提出了边染色图的单色树划分数的概念。r-边染色图G的单色树划分数,或简称为树划分数,记作t_r（G）,是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个顶点不交的单色树覆盖。Erd（o|¨）s,Gyarfas和Pyber猜想r-边染色完全图的单色树划分数是r-1,其中r≥2,并且他们证明了r=3时猜想的正确性。猜想对于r=2的情况等价于Erd（o|¨）s和Rado的断言:对任意的图G,图G和图G的补图至少有一个连通。对于无限完全图,Hajnal等人证明了一个r-边染色无限完全图的单色树划分数至多是r。对于有限完全图,Haxell和Kohayakawa证明了当n≥3r⁴r!（1-1/r）^3（1-r）logr,任意r-边染色完全图K_n含有至多r个两两不同色的单色树,并且他们的顶点集合划分了K_n的顶点集合。Haxell和Kohayakawa还证明了当n充分大时,r-边染色的完全二部图K_n,n的单色树划分数至多是2r。一般地,确定t_r（G）的精确的值是很困难的。与单色树划分数相关的一个问题是r-边染色图G的单色树覆盖数,或简称为树覆盖数,它是指最小的k满足:对于G的任意r-边染色,图G的顶点集合可被至多k个单色树（可以相交）覆盖。对于完全图,以某个点为中心的所有单色星构成了一个覆盖,所以r-边染色完全图的单色树覆盖数至多是r。Erd（o|¨）s,Gyarfas和Pyber关于树划分数的猜想的一个弱形式是:r-边染色完全图的单色树覆盖数是r-1。本文分为三部分,第一部分主要研究了2-边染色完全二部图的单色树划分问题,第二部分主要研究了3-边染色完全等部二部图的单色树划分问题,第三部分主要研究了2-边染色和3-边染色完全二部图的单色树覆盖问题。第二章中我们研究了2-边染色完全二部图的单色树划分。对于2-边染色的完全多部图K（n₁,n₂,…,n_k）,Kaneko,Kano和Suzuki证明了:设n₁,n₂,…,n_k（2≤k）是满足1≤n₁≤n₂≤…≤n_k的整数,并且n=n₁+n₂+…+n_k-1,m=n_k,则t₂（K（n₁,n₂,…,n_k））=（?）（m-3）/2ⁿ」+2。特别地,t₂(K_m,n)=（?）（m-2）/2ⁿ」+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）∈S₂,（4） K（A,B）∈S₁。2.如果K（A,B）∈M,则K（A,B）的顶点集可被两个同色的单色树覆盖;如果K（A,B）∈S₂,则K（A,B）的顶点集要么被一个孤立点和一个单色树覆盖,要么被两个不同色的顶点不交的单色树覆盖;如果K（A,B）∈S₁,并且m=|A|＞|B|=n,则K（A,B）的顶点集可被至多（?）（m-2）/2ⁿ」+2个顶点不交的单色树覆盖,并且存在边染色使K（A,B）的顶点集恰被（?）（m-2）/2ⁿ」+2个顶点不交的单色树覆盖。第三章中我们研究了3-边染色等部完全二部图的单色树划分。我们给出了几种色度条件下的单色树划分数。设K（A,B）是一个3-边染色等部完全二部图,我们得到如下结果。1.如果存在色度为1的顶点,则t₃（K（A,B））=3。2.如果每个顶点的色度都是2,则t₃（K（A,B））=2。3.如果每个顶点的色度都是3,则t₃（K（A,B））=3。4.如果每个顶点的色度都至少是2,并且恰有一个部有色度为3的顶点,则t₃（K（A,B））=4。第四章中我们研究了2-边染色和3-边染色完全二部图的单色树覆盖。我们的到了如下结果:1.2-边染色完全二部图的单色树覆盖数是2。2.3-边染色完全二部图的单色树覆盖数是4。更多还原

【Abstract】 Let G =（V（G）,E（G）） be a graph.By an edge coloring of G we mean a surjection C:E（G）→{1,2,…,r},the subset of natural numbers.If G is assigned such a coloring,then we say that G is an edge colored graph,or r-edge colored graph.Denote by C（e） the color of the edge e∈E.For each vertex v of G,the color neighborhood CN（v） of v is defined as the set {C（e）:e is incident with v} and the color degree is denoted by d^c（v）=|CN（v）|.A tree is called monochromatic if its any two edges have the same color.The monochromatic tree partition number,or simply tree partition number of an r-edge-colored graph G,denoted by t_r（G）,which was introduced by Erd（o|¨）s, Gyarfas and Pyber in 1991,is the minimum integer k such that whenever the edges of G are colored with r colors,the vertices of G can be covered by at most k vertex-disjoint monochromatic trees.Erd（o|¨）s,Gyarfas and Pyber conjectured that the tree partition number of an r-edge-colored complete graph is r-1,where r≥2.Moreover,they proved that the conjecture is true for r=3.For the case r=2, it is equivalent to the fact that for any graph G,either G or its complement is connected,an old remark of Erd（o|¨）s and Rado.For infinite complete graph,Hajnal et al proved that the tree partition number for an r-edge-colored infinite complete graph is at most r.For finite complete graph,Haxell and Kohayakawa proved that any r-edge-colored complete graph K_n contains at most r monochromatic trees,all of different colors,whose vertex sets partition the vertex set of K_n, provided n≥3r⁴r!（1-1/r）^3（1-r）log r.Haxell and Kohayakawa also proved that the tree partition number for an r-edge-colored complete bipartite graph K_n,n is at most 2r,provided n is sufficiently large.In general,to determine the exact value of t_r（G） is very difficult.A problem that is related to tree partitioning is to find the monochromatic tree cover number,or simply tree cover number for r-edge-colored graphs,the minimum number k such that the vertices of an r-edge-colored graph can be covered by k（not necessarily disjoint） monochromatic trees.It is obvious that the tree cover number of an r-edge-colored complete graph is at most r since the monochromatic stars at any vertex give a covering.A weaker form of tree partition conjecture introduced by Erd（o|¨）s,Gyarfas and Pyber is:the tree cover number of an r-edge-colored complete graph is r-1.This thesis consists of three parts.In the first part,we investigate the problem of the tree partition number of 2-edge-colored complete bipartite graphs. In the second part,we consider the problem of the tree partition number of 3-edge-colored complete equi-bipartite graphs.The last part is contributed to the problem of the tree cover number of 2-edge-colored complete bipartite graphs and 3-edge-colored complete bipartite graphs.In Chapter 2,we characterize the tree partition number of 2-edge-colored complete bipartite graphs.For 2-edge-colored complete multipartite graph K（n₁,n₂,…,n_k）,Kaneko,Kano,and Suzuki[34]proved the following result: Let n₁,n₂,…n_k（k≥2） be integers such that 1≤n₁＜n₂≤…≤n_k,and let n=n₁+n₂+…+n_k-1 and m=n_k.Then t₂（K（n₁,n₂,…,n_k））=[（m-2）/2ⁿ]+2.In particular,they proved that t₂(K_m,n)=[（m-2）/2ⁿ]+2 where 1≤n≤m.In 2006,Jin et al[31]gave a polynomial-time algorithm to partition a 2-edge-colored complete multipartite graph into monochromatic trees.In this chapter,we give a description to partition a 2-edge-colored complete bipartite graph into monochromatic trees in more detail.To be precise,we distinguish four structures of 2-edge-colored complete bipartite graphs,and give the exact tree partition mumber for each case:1.If K（A,B） is a 2-edge-colored complete bipartite graph,then it has one of the following four structures:（1） K（A,B） has a monochromatic spanning tree;（2） K（A,B）∈M;（3） K（A,B）∈S₂;（4） K（A,B）∈S₁.2.If K（A,B）∈M,then the vertices of K（A,B） can be covered by two vertex-disjoint monochromatic trees with the same color;if K（A,B）∈S₂,then the vertices of K（A,B） can be covered by either an isolated vertex and a monochromatic tree or two vertex-disjoint monochromatic trees with different colors;if K（A,B）∈S₁ and m= |A|＞|B|=n,the vertices of K（A,B） can be covered by at most[（m-2）/2ⁿ]+2 vertex-disjoint monochromatic trees,and there exists an edge coloring such that the vertices of K（A,B） are covered by exactly[（m-2）/2ⁿ]+2 vertex- disjoint monochromatic trees.In Chapter 3,we discuss the tree partition number of 3-edge-colored complete equi-bipartite graphs.We give the tree partition number under some color degree conditions.Let K（A,B） be a 3-edge-colored complete equi-bipartite graph,the following results are obtained.1.If K（A,B） has at least one vertex with color degree 1,then t₃（K（A,B））=3.2.If every vertex of K（A,B） has color degree 2,then t₃（K（A,B））=2.3.If every vertex of K（A,B） has color degree 3,then t₃（K（A,B））=3.4.If every vertex of K（A,B） has color degree at least 2,and exactly one partite set has vertex with color degree 3,then t₃（K（A,B））=4.The Chapter 4 is attributed to the tree cover number of 2-edge-colored complete bipartite graphs and 3-edge-colored complete bipartite graphs.We prove:1.The tree cover number of a 2-edge-colored complete bipartite graph is 2.2.The tree cover number of a 3-edge-colored complete bipartite graph is 4.更多还原