Publications
Sort:
Issue
Monochromatic Cycles and Trees in Edge-Colored Complete Graphs
Journal of Xinjiang University(Natural Science Edition in Chinese and English) 2022, 39(1): 16-18,41
Published: 01 January 2022
Abstract PDF (1.9 MB) Collect
Downloads:12

Let f(r,n) be the maximum integer k such that every r-edge-colored complete graph Kn contains a monochromatic cycle of length at least k. In 2009, Faudree, Lesniak and Schiermeyer conjectured that every (r+1)-edge-colored complete graph Kn contains a monochromatic cycle of length at least nr for r ≥ 2. Meanwhile, they also proved that f(2,n) ≥ 2n3 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 Kn contains a monochromatic cycle of length at least nr for 1 ≤ r ≤ n. In this paper, we disprove this conjecture for n=rt+1, where r ≥ 2 and n1r is a positive even integer. More precisely, there exists a (r+1)-edge-colored complete graph Kn contains a monochromatic cycle of length less than nr. For a k-edge coloring c of Kn, let moc(Kn,c) be the largest order of monochromatic tree of Kn under c. Let moc(n,k) = min{moc(Kn,c): c is a k-edge coloring of Kn}. We show that for any positive integer n ≥ 3, moc(n,3) = n2 if n ≡ 0,1 (mod 4) and moc(n, 3) = n+12 if n ≡ 2,3 (mod 4).

Total 1