Monochromatic Tree Partition Of Complete Bipartite Graphs And Monochrome Tree Cover

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.