Monochromatic Cycles in 2-Coloured Graphs

Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree delta(G) > 3n/4 contains a monochromatic cycle of length l, for all l is an element of [4, [n/2]]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with delta(G) = 3n/4 that do not contain all such cycles. Finally, we show that, for all delta > 0 and n > n(0)(delta), if G is a 2-edge coloured graph of order n with delta(G) >= 3n/4, then one colour class either contains a monochromatic cycle of length at least (2/3 + delta/2)n, or contains monochromatic cycles of all lengths l is an element of [3, (2/3 - delta)n].