2011/07/26 by Alex Scott, Scott, Alex, Matthew White +1
Computer Science · Mathematics · #05C38 (Primary) 05C55 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C38 #msc:05C55
paper · pdf · doi:10.48550/arxiv.1107.5177
35 pages, 2 figures. Submitted to CPC
arxiv created 2011/07/26 · openalex publication_date 2011/07/26 · arxiv updated 2011/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Li, Nikiforov and Schelp conjectured that a 2-edge coloured graph G with order n and minimal degree strictly greater than 3n/4 contains a monochromatic cycle of length l, for all l at least four and at most n/2. We prove this conjecture for sufficiently large n and also find all 2-edge coloured graphs with minimal degree equal to 3n/4 that do not contain all such cycles. Finally we show that, for all positive constants d and sufficiently large n, a 2-edge coloured graph G of order n with minimal degree at least 3n/4 either contains a monochromatic cycle of length at least (2/3+d/2)n, or, in one of the two colours, contains a cycle of all lengths between three and (2/3-d)n.