Combinatorics Probability Computing · 2012 · 32 citations · 12 references
Natural SciencesEvolutionary BiologyColor TheoryCombinatoricsCytogeneticsDirected Acyclic GraphsGraph ColoringGraph Theory
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 ].
12
Some Theorems on Abstract Graphs
G. A. Dirac · Proceedings of the London Mathematical Society · 1952 · 1.6K citations
The Factorization of Linear Graphs
W. T. Tutte · Journal of the London Mathematical Society · 1947 · 939 citations
On maximal paths and circuits of graphs
P. Erdös · Acta Mathematica Academiae Scientiarum Hungaricae · 1959 · 903 citations
Endre Szemerédi · Defense Technical Information Center (DTIC) · 1975 · 806 citations