Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles

• Verfasst von: Arras, Patrick [VerfasserIn]
• Titel: Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Verf.angabe: Patrick Arras
• E-Jahr: 2023
• Jahr: May 5, 2023
• Umfang: 1-31$t31
• Fussnoten: Gesehen am 27.06.2023
• Titel Quelle: Enthalten in: The electronic journal of combinatorics
• Ort Quelle: [Madralin] : EMIS ELibEMS, 1994
• Jahr Quelle: 2023
• Band/Heft Quelle: 30(2023), 2 vom: Mai, Artikel-ID P2.18
• ISSN Quelle: 1077-8926
• DOI: doi:10.37236/11052
• Datenträger: Online-Ressource
• Sprache: eng
• K10plus-PPN: 1851070559

Abstract

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) \geq 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.