Monochromatic Cycles and Trees in Edge-Colored Complete Graphs

Let f(r,n) be the maximum integer k such that every r-edge-colored complete graph K_n contains a monochromatic cycle of length at least k. In 2009, Faudree, Lesniak and Schiermeyer conjectured that every (r+1)-edge-colored complete graph K_n contains a monochromatic cycle of length at least $\frac{n}{r}$ for r ≥ 2. Meanwhile, they also proved that f(2,n) ≥ $\lceil \frac{2n}{3}\rceil$ for n ≥ 6, and this bound is sharp. In 2011, Fujita disproved this conjecture for n=2r and also showed that every r-edge-colored complete graph K_n contains a monochromatic cycle of length at least $\frac{n}{r}$ for 1 ≤ r ≤ n. In this paper, we disprove this conjecture for n=rt+1, where r ≥ 2 and $\frac{n-1}{r}$ is a positive even integer. More precisely, there exists a (r+1)-edge-colored complete graph K_n contains a monochromatic cycle of length less than $\frac{n}{r}$. For a k-edge coloring c of K_n, let moc(K_n,c) be the largest order of monochromatic tree of K_n under c. Let moc(n,k) = min{moc(K_n,c): c is a k-edge coloring of K_n}. We show that for any positive integer n ≥ 3, moc(n,3) = $\lceil \frac{n}{2}\rceil$ if n ≡ 0,1 (mod 4) and moc(n, 3) = $\lceil \frac{n+1}{2}\rceil$ if n ≡ 2,3 (mod 4).