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 $\mathrm{deg}(u)+\mathrm{deg}(v)\ge 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.

25 pages, 1 figure, final version

References in corpus (1)

• Tiling with monochromatic bipartite graphs of bounded maximum degree