Monochromatic cycle partitions - an exact result

17 February 2015
Shoham Letzter
In 2011, Schelp introduced the idea of considering Ramsey-Turán type problems for graphs with large minimum degree. Inspired by his questions, Balogh, Barat, Gerbner, Gyárfás, and Sárközy suggested the following conjecture. Let $G$ be a graph on $n$ vertices with minimum degree at least $3n/4$. Then for every red and blue colouring of the edges of $G$, the vertices of $G$ may be partitioned into two vertex-disjoint cycles, one red and the other blue. They proved an approximate version of the conjecture, and recently DeBiasio and Nelsen obtained stronger approximate results. We prove the conjecture exactly (for large $n$). I will give an overview of the history of this problem and describe some of the tools that are used for the proof. I will finish with a discussion of possible future work for which the methods we use may be applicable.
  • Combinatorial Theory Seminar