Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles - Arras, Patrick (The electronic journal of combinatorics, 2023)
In 2019, Letzter confirmed a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy, proving that every large 222-edge-coloured graph GGG on nnn vertices with minimum degree at least 3n/43n/43n/4 can be partitioned into two monochromatic cycles of different colours. Here, we propose a weaker condition on the degree sequence of GGG 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 deg(u)+deg(v)≥4n/3+o(n)deg⁡(u)+deg⁡(v)≥4n/3+o(n)\operatorname{deg}(u) + \operatorname{deg}(v) ≥ 4n/3 + o(n) holds for all non-adjacent vertices u,v∈V(G)u,v∈V(G)u,v \in V(G), then all but o(n)o(n)o(n) vertices can be partitioned into three monochromatic cycles.
Gesehen am 27.06.2023