完全二部图的单色树划分和单色树覆盖
|
摘要
一个图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~4r!(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_1,n_2,…,n_k),Kaneko,Kano和Suzuki证明了:设n_1,n_2,…,n_k(2≤k)是满足1≤n_1≤n_2≤…≤n_k的整数,并且n=n_1+n_2+…+n_(k-1),m=n_k,则t_2(K(n_1,n_2,…,n_k))=(?)(m-3)/2~n」+2。特别地,t_2(K_(m,n))=(?)(m-2)/2~n」+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_2,(4) K(A,B)∈S_1。
2.如果K(A,B)∈M,则K(A,B)的顶点集可被两个同色的单色树覆盖;如果K(A,B)∈S_2,则K(A,B)的顶点集要么被一个孤立点和一个单色树覆盖,要么被两个不同色的顶点不交的单色树覆盖;如果K(A,B)∈S_1,并且m=|A|＞|B|=n,则K(A,B)的顶点集可被至多(?)(m-2)/2~n」+2个顶点不交的单色树覆盖,并且存在边染色使K(A,B)的顶点集恰被(?)(m-2)/2~n」+2个顶点不交的单色树覆盖。
第三章中我们研究了3-边染色等部完全二部图的单色树划分。我们给出了几种色度条件下的单色树划分数。设K(A,B)是一个3-边染色等部完全二部图,我们得到如下结果。
1.如果存在色度为1的顶点,则t_3(K(A,B))=3。
2.如果每个顶点的色度都是2,则t_3(K(A,B))=2。
3.如果每个顶点的色度都是3,则t_3(K(A,B))=3。
4.如果每个顶点的色度都至少是2,并且恰有一个部有色度为3的顶点,则t_3(K(A,B))=4。
第四章中我们研究了2-边染色和3-边染色完全二部图的单色树覆盖。我们的到了如下结果:
1.2-边染色完全二部图的单色树覆盖数是2。
2.3-边染色完全二部图的单色树覆盖数是4。
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~4r!(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_1,n_2,…,n_k),Kaneko,Kano,and Suzuki[34]proved the following result: Let n_1,n_2,…n_k(k≥2) be integers such that 1≤n_1＜n_2≤…≤n_k,and let n=n_1+n_2+…+n_(k-1) and m=n_k.Then t_2(K(n_1,n_2,…,n_k))=[(m-2)/2~n]+2.In particular,they proved that t_2(K_(m,n))=[(m-2)/2~n]+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_2;(4) K(A,B)∈S_1.
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_2,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_1 and m= |A|＞|B|=n,the vertices of K(A,B) can be covered by at most[(m-2)/2~n]+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~n]+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_3(K(A,B))=3.
2.If every vertex of K(A,B) has color degree 2,then t_3(K(A,B))=2.
3.If every vertex of K(A,B) has color degree 3,then t_3(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_3(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.
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~4r!(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_1,n_2,…,n_k),Kaneko,Kano和Suzuki证明了:设n_1,n_2,…,n_k(2≤k)是满足1≤n_1≤n_2≤…≤n_k的整数,并且n=n_1+n_2+…+n_(k-1),m=n_k,则t_2(K(n_1,n_2,…,n_k))=(?)(m-3)/2~n」+2。特别地,t_2(K_(m,n))=(?)(m-2)/2~n」+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_2,(4) K(A,B)∈S_1。
2.如果K(A,B)∈M,则K(A,B)的顶点集可被两个同色的单色树覆盖;如果K(A,B)∈S_2,则K(A,B)的顶点集要么被一个孤立点和一个单色树覆盖,要么被两个不同色的顶点不交的单色树覆盖;如果K(A,B)∈S_1,并且m=|A|＞|B|=n,则K(A,B)的顶点集可被至多(?)(m-2)/2~n」+2个顶点不交的单色树覆盖,并且存在边染色使K(A,B)的顶点集恰被(?)(m-2)/2~n」+2个顶点不交的单色树覆盖。
第三章中我们研究了3-边染色等部完全二部图的单色树划分。我们给出了几种色度条件下的单色树划分数。设K(A,B)是一个3-边染色等部完全二部图,我们得到如下结果。
1.如果存在色度为1的顶点,则t_3(K(A,B))=3。
2.如果每个顶点的色度都是2,则t_3(K(A,B))=2。
3.如果每个顶点的色度都是3,则t_3(K(A,B))=3。
4.如果每个顶点的色度都至少是2,并且恰有一个部有色度为3的顶点,则t_3(K(A,B))=4。
第四章中我们研究了2-边染色和3-边染色完全二部图的单色树覆盖。我们的到了如下结果:
1.2-边染色完全二部图的单色树覆盖数是2。
2.3-边染色完全二部图的单色树覆盖数是4。
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~4r!(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_1,n_2,…,n_k),Kaneko,Kano,and Suzuki[34]proved the following result: Let n_1,n_2,…n_k(k≥2) be integers such that 1≤n_1＜n_2≤…≤n_k,and let n=n_1+n_2+…+n_(k-1) and m=n_k.Then t_2(K(n_1,n_2,…,n_k))=[(m-2)/2~n]+2.In particular,they proved that t_2(K_(m,n))=[(m-2)/2~n]+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_2;(4) K(A,B)∈S_1.
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_2,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_1 and m= |A|＞|B|=n,the vertices of K(A,B) can be covered by at most[(m-2)/2~n]+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~n]+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_3(K(A,B))=3.
2.If every vertex of K(A,B) has color degree 2,then t_3(K(A,B))=2.
3.If every vertex of K(A,B) has color degree 3,then t_3(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_3(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.
引文
[1] S. Akbari and A. Alipour, Multicolored trees in complete graphs, J. Graph Theory 54 (2006), 221-232.
[2] N. Alon, R.A. Brualdi and B.L. Shader, Multicolored forests in bipartite decompositions of graphs, J. Combin. Theory Ser. B 53 (1991), 143-148.
[3] M. Albert, A. Frieze and B. Reed, Multicolored Hamilton cycles, Electronic J. Combin. 2 (1995), # R10.
[4] R.A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs, J. Combin. Theory Ser. B 68 (1996), 310-313.
[5] R.A. Brualdi and S. Hollingsworth, Multicolored forests in complete bipartite graphs, J. Discrete Math. 240 (2001), 239-245.
[6] H.J. Broersma and X.L. Li, Spanning trees with many or few colors in edge-colored graphs, Discuss. Math. Graph Theory 17 (1997), 259-269.
[7] H.J. Broersma, X.L. Li, G. Woeginger and S. Zhang, Paths and cycles in colored graphs, Australasian J. Combin. 31 (2005), 297-309.
[8] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan London and Elsvier, New York (1976).
[9] G.M. Constantine, Colorful isomorphic spanning trees in complete graphs, Ann. Combin. 9 (2005), 163-167.
[10] H. Chen and X.L. Li, Long heterochromatic paths in edge-colored graphs, Electronic J. Combin. 12 (2005), # R33.
[11] H. Chen and X.L. Li, Color degree condition for long heterochromatic paths in edge-colored graphs, arXiv:math.CO/0512144, 7 Dec 2005.
[12] H. Chen and X.L. Li, Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs, Electronic J. Combin. 14 (2007), #R77.
[13] H. Chen, Z.M. Jin, X.L. Li and J.H. Tu, Heterchromatic tree partition numbers for complete bipartite graphs, J. Discrete Math. (2007), doi:10.1016/j.disc.2007.07.085.
[14] P. Erdos, and F. Galvin, Monochromatic infinite paths, J. Discrete Math. 113 (1993), 59-70.
[15] P. Erdos, A. Gyarfas and L. Pyber, Vertex coverings by monochromatic cycles and trees, J. Combin. Theory Ser. B 51 (1991), 90-95.
[16] Z. Füredi, Maximum degree and fractional mathchings in uniform hyper-graphs, Combinatorica 1 (1981), 155-162.
[17] Z. Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206.
[18] M.R. Garey and D.S. Johnson, Computers and Intractability, W.H. Freeman, San Francisco, 1979.
[19] L. Gerencser and A. Gyarfas, On Ramsey-type problems, Ann. Univ. Sci. Bud. de Rol. Eotvos Sect. Math. 10 (1967), 167-170.
[20] A. Gyarfas, Partition coverings and blocking sets in hypergraphs (in Hungarian), in "MTA SZTAKI studies," 71 (1977) (MR58,5392).
[21] A. Gyarfas, Vertex coverings by monochromatic paths and cycles, J. Graph Theory 7 (1983), 131-135.
[22] A. Gyarfas, Covering complete graphs by monochromatic paths, in Irregularities of Partitions, Algorithms and Combinatorics, Springer Verlag 8 (1989), 89-91.
[23] A. Gyarfas, A. Jagota and R.H. Schelp, Monochromatic path covers in nearly complete graphs, J. Combin. Math. Combin. Comput. 25 (1997), 129-144.
[24] A. Gyarfas, M. Ruszinko, G.N. Sarkozy and E. Szemerédi, An improved bound for the monochromatic cycle partiton number, J. Combin. Theory Ser. B 96 (2006), 855-873.
[25] A. Gyarfas and G.N. Sarkozy, Size of monochromatic double stars in edge colorings, Graphs and Combin. 24 (2008), 531-536.
[26] A. Gyarfas and G. Simony, Edge coloring of complete graphs without tricol-ored triangles, J. Graph Theory 46 (2004), 211-216.
[27] A. Hajnal, P. Komjath, L. Soukup and I. Szalkai, Decompositions of edge colored infinite complete graphs, Colloq. Math. Soc. Janos Bolyai 52 (1987), 277-280.
[28] P.E. Haxell and Y. Kohayakawa, Partitioning by monochromatic trees, J. Combin. Theory Ser. B 68 (1996), 218-222.
[29] P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles, J. Combin. Theory Ser. B 69 (1997), 210-218.
[30] G. Hahn and C. Thomassen, Path and cycle sub-Ramsey numbers and an edge-coloring conjecture, J. Discrete Math. 62 (1986), 29-33.
[31] Z.M. Jin, M. Kano, X.L. Li and B. Wei, Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees, J. Comb. Optim 11 (2006), 445-454.
[32] Z.M. Jin and X.L. Li, The complexity for partitioning graphs by monochromatic trees, cycles and paths, Int. J. Comput. Math. 81 (2004), 1357-1362.
[33] Z.M. Jin and X.L. Li, Vertex partitions of r-edge-colored graphs, Appl. Math. J. Chinese Univ. 23 (1) (2008), 120-126.
[34] A. Kaneko, M. Kano and K. Suzuki, Partitioning complete multipartite graphs by monochromatic trees, J. Graph Theory 48 (2005), 133-141.
[35]M.Kano and X.Li,Monochromatic and heterochromatic subgraphs in edgecolored graphs-a survey,Graphs and Combin.24(4)(2008),237-263.
[36]T.Luczak,V.R(o|¨)dl and E.Szemeredi,Partitioning two-colored complete graphs into two monochromatic cycles,Probab.Combin.Comput.7(1998),423-436.
[37]X.L.Li and X.Y.Zhang,On the minimum monochromatic or multicolored subgraph partition problems,Theoretical computer science 385(1-3)(2007),1-10.
[38]L.Pyber,V.R(o|¨)dl and E.Szemeredi,Dense graphs without 3-regular subgraphs,J.Combin Ser.B 63(1995),41-54.
[39]R.Rado,Monochromatic paths in graphs,Ann.Discrete Math.3(1978),191-194.
[40]K.Suzuki,A necessary and sufficient condition for the exience of a heterochromatic spannng tree in a graph,Graphs Combin.22(2006),261-269.
[41]G.N.Sark(o|¨)zy and S.M.Selkow,Vertex partitions by connected monochromatic k-regular graphs,J.Combin.Theory Ser.B 78(2000),115-122.
[42]Zs.Tuza,Some special cases of Rysers Conjecture(1978),Preprint.
[43]C.Thomassen,Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5,J.Combin.Theory Ser.B 75(1999),100-109.
[2] N. Alon, R.A. Brualdi and B.L. Shader, Multicolored forests in bipartite decompositions of graphs, J. Combin. Theory Ser. B 53 (1991), 143-148.
[3] M. Albert, A. Frieze and B. Reed, Multicolored Hamilton cycles, Electronic J. Combin. 2 (1995), # R10.
[4] R.A. Brualdi and S. Hollingsworth, Multicolored trees in complete graphs, J. Combin. Theory Ser. B 68 (1996), 310-313.
[5] R.A. Brualdi and S. Hollingsworth, Multicolored forests in complete bipartite graphs, J. Discrete Math. 240 (2001), 239-245.
[6] H.J. Broersma and X.L. Li, Spanning trees with many or few colors in edge-colored graphs, Discuss. Math. Graph Theory 17 (1997), 259-269.
[7] H.J. Broersma, X.L. Li, G. Woeginger and S. Zhang, Paths and cycles in colored graphs, Australasian J. Combin. 31 (2005), 297-309.
[8] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, Macmillan London and Elsvier, New York (1976).
[9] G.M. Constantine, Colorful isomorphic spanning trees in complete graphs, Ann. Combin. 9 (2005), 163-167.
[10] H. Chen and X.L. Li, Long heterochromatic paths in edge-colored graphs, Electronic J. Combin. 12 (2005), # R33.
[11] H. Chen and X.L. Li, Color degree condition for long heterochromatic paths in edge-colored graphs, arXiv:math.CO/0512144, 7 Dec 2005.
[12] H. Chen and X.L. Li, Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs, Electronic J. Combin. 14 (2007), #R77.
[13] H. Chen, Z.M. Jin, X.L. Li and J.H. Tu, Heterchromatic tree partition numbers for complete bipartite graphs, J. Discrete Math. (2007), doi:10.1016/j.disc.2007.07.085.
[14] P. Erdos, and F. Galvin, Monochromatic infinite paths, J. Discrete Math. 113 (1993), 59-70.
[15] P. Erdos, A. Gyarfas and L. Pyber, Vertex coverings by monochromatic cycles and trees, J. Combin. Theory Ser. B 51 (1991), 90-95.
[16] Z. Füredi, Maximum degree and fractional mathchings in uniform hyper-graphs, Combinatorica 1 (1981), 155-162.
[17] Z. Füredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115-206.
[18] M.R. Garey and D.S. Johnson, Computers and Intractability, W.H. Freeman, San Francisco, 1979.
[19] L. Gerencser and A. Gyarfas, On Ramsey-type problems, Ann. Univ. Sci. Bud. de Rol. Eotvos Sect. Math. 10 (1967), 167-170.
[20] A. Gyarfas, Partition coverings and blocking sets in hypergraphs (in Hungarian), in "MTA SZTAKI studies," 71 (1977) (MR58,5392).
[21] A. Gyarfas, Vertex coverings by monochromatic paths and cycles, J. Graph Theory 7 (1983), 131-135.
[22] A. Gyarfas, Covering complete graphs by monochromatic paths, in Irregularities of Partitions, Algorithms and Combinatorics, Springer Verlag 8 (1989), 89-91.
[23] A. Gyarfas, A. Jagota and R.H. Schelp, Monochromatic path covers in nearly complete graphs, J. Combin. Math. Combin. Comput. 25 (1997), 129-144.
[24] A. Gyarfas, M. Ruszinko, G.N. Sarkozy and E. Szemerédi, An improved bound for the monochromatic cycle partiton number, J. Combin. Theory Ser. B 96 (2006), 855-873.
[25] A. Gyarfas and G.N. Sarkozy, Size of monochromatic double stars in edge colorings, Graphs and Combin. 24 (2008), 531-536.
[26] A. Gyarfas and G. Simony, Edge coloring of complete graphs without tricol-ored triangles, J. Graph Theory 46 (2004), 211-216.
[27] A. Hajnal, P. Komjath, L. Soukup and I. Szalkai, Decompositions of edge colored infinite complete graphs, Colloq. Math. Soc. Janos Bolyai 52 (1987), 277-280.
[28] P.E. Haxell and Y. Kohayakawa, Partitioning by monochromatic trees, J. Combin. Theory Ser. B 68 (1996), 218-222.
[29] P.E. Haxell, Partitioning complete bipartite graphs by monochromatic cycles, J. Combin. Theory Ser. B 69 (1997), 210-218.
[30] G. Hahn and C. Thomassen, Path and cycle sub-Ramsey numbers and an edge-coloring conjecture, J. Discrete Math. 62 (1986), 29-33.
[31] Z.M. Jin, M. Kano, X.L. Li and B. Wei, Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees, J. Comb. Optim 11 (2006), 445-454.
[32] Z.M. Jin and X.L. Li, The complexity for partitioning graphs by monochromatic trees, cycles and paths, Int. J. Comput. Math. 81 (2004), 1357-1362.
[33] Z.M. Jin and X.L. Li, Vertex partitions of r-edge-colored graphs, Appl. Math. J. Chinese Univ. 23 (1) (2008), 120-126.
[34] A. Kaneko, M. Kano and K. Suzuki, Partitioning complete multipartite graphs by monochromatic trees, J. Graph Theory 48 (2005), 133-141.
[35]M.Kano and X.Li,Monochromatic and heterochromatic subgraphs in edgecolored graphs-a survey,Graphs and Combin.24(4)(2008),237-263.
[36]T.Luczak,V.R(o|¨)dl and E.Szemeredi,Partitioning two-colored complete graphs into two monochromatic cycles,Probab.Combin.Comput.7(1998),423-436.
[37]X.L.Li and X.Y.Zhang,On the minimum monochromatic or multicolored subgraph partition problems,Theoretical computer science 385(1-3)(2007),1-10.
[38]L.Pyber,V.R(o|¨)dl and E.Szemeredi,Dense graphs without 3-regular subgraphs,J.Combin Ser.B 63(1995),41-54.
[39]R.Rado,Monochromatic paths in graphs,Ann.Discrete Math.3(1978),191-194.
[40]K.Suzuki,A necessary and sufficient condition for the exience of a heterochromatic spannng tree in a graph,Graphs Combin.22(2006),261-269.
[41]G.N.Sark(o|¨)zy and S.M.Selkow,Vertex partitions by connected monochromatic k-regular graphs,J.Combin.Theory Ser.B 78(2000),115-122.
[42]Zs.Tuza,Some special cases of Rysers Conjecture(1978),Preprint.
[43]C.Thomassen,Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5,J.Combin.Theory Ser.B 75(1999),100-109.