The minimum color degree and a large rainbow cycle in an edge-colored graph

Publication date: 20 September 2021

Abstract: 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 i n 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

f r a c n + 3 k - 2 2

, then

G

contains a rainbow-cycle subgraph of length at least

k

, where

k g e q 5

. Moreover, if the condition of

G

is restricted to a triangle-free graph that contains a rainbow path of length at least

f r a c 3 k 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

f r a c 2 n + 3 k - 1 4

.

Cited In (2)

This page was built for publication: The minimum color degree and a large rainbow cycle in an edge-colored graph