Research On The 3-Rainbow Index Of Graphs

Chartrand, Okamoto and Zhang proposed the concept of k-rainbow coloring in 2009. Let G be a nontrivial connected graph with an edge-coloring c:E(G) ? {1,2,..., k}, k ? N. An edge-colored tree T in G is a rainbow tree if no two edges of T are assigned the same color. A k-rainbow coloring of G is an edge coloring of G having the property that for every set S of k vertices of G, there exists a rainbow tree T in G such that S (?) V(T). The minimum number of colors needed in a k-rainbow coloring of G is the k-rainbow index of G, denoted by rxk(G). We focus on 3-rainbow index in the text.The full text is divided into six parts.In the first part, we briefly introduce the research background, definitions, structure and main conclusion of the paper.In the second part, we present some concepts, symbol marks and related prelimi-nary knowledge needed in the proof.In the third part, we study some upper bounds of 3-rainbow index of graphs.We first show that 3-rainbow index of any connected graph G of order n is bound up with dominating set of G. By this conclusion, we obtain an sharp upper bound for 3-rainbow index of Ks,t 3? s? t. And we deduce the exact value of rx3 (K2,t) with board method. Then we determine a better bound for (P5, C5)-free graphs. Finally, a sharp bound for 3-rainbow index of general graphs is obtained.In the forth part, we consider the 3-rainbow index of graph operations.In this part, we obtain the 3-rainbow index rx3(G) with respect to important graph product operations (namely cartesian product, strong product, lexicographic product, the join of two graphs, split a vertex of a graph and subdivide an edge of a graph) and present sufficient condition for the upper bound of lexicographic product.In the fifth part, we concentrate on 3-rainbow coloring of split graphs.In this part, we almost obtain a 3-rainbow coloring of split graphs by an algorithm. The algorithm constructs an appropriate coloring of split graphs based on the analysis of the necessary condition of -rainbow coloring. And the number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.In the sixth part, we get the conclusion and summary of this paper and outlook of the future.