Ore- and Pósa-Type Conditions for Partitioning 2-Edge-Coloured Graphs into Monochromatic Cycles

Abstract

In 2019, Letzter confirmed a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy, proving that every large $2$-edge-coloured graph $G$ on $n$ vertices with minimum degree at least $3n/4$ can be partitioned into two monochromatic cycles of different colours. Here, we propose a weaker condition on the degree sequence of $G$ to also guarantee such a partition and prove an approximate version. This resembles a similar generalisation to an Ore-type condition achieved by Barát and Sárközy.

Continuing work by Allen, Böttcher, Lang, Skokan and Stein, we also show that if $\operatorname{deg}(u) + \operatorname{deg}(v) \geq 4n/3 + o(n)$ holds for all non-adjacent vertices $u,v \in V(G)$, then all but $o(n)$ vertices can be partitioned into three monochromatic cycles.