Some Results On Rainbow Graphs

An edge coloring of a graph G=(V, E) is a map c:Eâ†'S, where S∈N is a color set. An edge-colored graph is denoted by (G, c).(H, c) is called a rainbow subgraph of (G,c) if H is a subgraph of G and c(e)≠c(f) for any two distinct edges e,f∈E(H). The color degree of v∈V, denoted by d(Ï…), is the number of different colors on edges incident to v, the maximum color degree and the minimum color degree are respectively denoted byâ–³(G) and δ(G). A rainbow matching of (G,c) is a matching in which no two edges have the same color. A rainbow domination set of (G, c) is a set of disjoint rainbow stars needed to cover V(G). Given an edge-colored graph (G,c), a rainbow path and a rainbow cycle are respectively a path and a cycle whose edges have distinct colors. An edge-colored graph (G, c) is called rainbow connected if for x, y∈V, there exists a rainbow path which connects x and y. In this dissertation, we firstly introduce some known results on rainbow matching and rainbow domination, then we try to explore some new results on rainbow graphs. Our main results are as follows:(1) An edge-colored graph (G,c) contains a rainbow path of length at least［δ(G)/2ï¼½;(2)(G, c) contains either a rainbow path of length at least ï¼»3δ(G)/4ï¼½ or a rainbow cycle of length at least ［δ(G)/4ï¼½+2;(3) Some necessary conditions for the rainbow connection of the edge-colored unicyclic graphs;(4) Given an edge-colored graph (G, c) with order n≥3, if δ(G)≥n/2, then(G,c) contains a non-monochromatic hamilton cycle. This result is a generalization of the Dirac condition on hamilton cycles;(5) Let (G, c) be an edge-colored graph with order n≥4, and G is not a complete graph, if for any two distinct vertices x, y∈V where xy(?)E(G), d(x)+d(y)≥n, then (G, c) contains a non-monochromatic hamilton cycle. This result is a generalization of the Ore condition on hamilton cycles;(6) Discussion on the Konig theroem in the edge-colored bipartite graphs.