Monochromatic Cycles in 2-Coloured Graphs

Fabrício Benevides, Tomasz Łuczak, Alex Scott, Jozef Skokan, Matthew White

Combinatorics Probability Computing · 2012 · 32 citations · 12 references

DOIFull text

Open access

Concepts

Abstract

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 ].

References

12