Monochromatic odd cycles in edge-coloured complete graphs

2024/12/10 by António Girão, Zach Hunter, Girão, António +1 · 2 citations
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.2412.07708

Abstract

It is easy to see that every q-edge-colouring of the complete graph on 2^q+1 vertices must contain a monochromatic odd cycle. A natural question raised by Erdős and Graham in 1973 asks for the smallest L(q) such that every q-edge-colouring of K_2^q+1 must contain a monochromatic odd cycle of length at most L(q). In here, we show that L(q)=O(\frac2^qq^1-o(1)) giving the first non-trivial upper bound on L(q).

Cited by

• An improved upper bound for the multicolour Ramsey number of odd cycles
• Short monochromatic odd cycles

Related

• Short monochromatic odd cycles
• Multicolour Ramsey Numbers of Odd Cycles
• Monochromatic cycles and the monochromatic circumference in 2-coloured graphs
• Exact Ramsey numbers of odd cycles via nonlinear optimisation
• Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles