2017/08/14 by Wipawee Tangjai, Tangjai, Wipawee
Computer Science · Engineering · Mathematics · #05C15 #05C38 #05C78 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1708.04187
openalex publication_date 2017/08/14 · openalex created_date 2017/08/31 · openalex updated_date 2026/07/28
Let G be an edge-colored graph with n vertices. A subgraph H of G is called a rainbow subgraph of G if the colors of each pair of the edges in E(H) are distinct. We define the minimum color degree of G to be the smallest number of the colors of the edges that are incident to a vertex v, for all v∈ V(G). Suppose that G contains no rainbow-cycle subgraph of length four. We show that if the minimum color degree of G is at least (n+3k-2)/(2), then G contains a rainbow-cycle subgraph of length at least k, where k≥ 5. Moreover, if the condition of G is restricted to a triangle-free graph that contains a rainbow path of length at least (3k)/(2), then the lower bound of the minimum color degree of G that guarantees an existence of a rainbow-cycle subgraph of length to at least k can be reduced to (2n+3k-1)/(4).