Type: Article
Publication Date: 2012-03-01
Citations: 36
DOI: https://doi.org/10.1017/s0963548312000090
Li, Nikiforov and Schelp [13] conjectured that any 2-edge coloured graph G with order n and minimum degree δ( G ) > 3 n /4 contains a monochromatic cycle of length ℓ, for all ℓ ∈ [4, ⌈ n /2⌉]. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with δ( G )=3 n /4 that do not contain all such cycles. Finally, we show that, for all δ>0 and n > n 0 (δ), if G is a 2-edge coloured graph of order n with δ( G ) ≥ 3 n /4, then one colour class either contains a monochromatic cycle of length at least (2/3+δ/2) n , or contains monochromatic cycles of all lengths ℓ ∈ [3, (2/3−δ) n ].