Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
May 5, 2023
|
| In: |
The electronic journal of combinatorics
Year: 2023, Volume: 30, Issue: 2 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/11052 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.37236/11052 Verlag, lizenzpflichtig, Volltext: https://www.combinatorics.org/ojs/index.php/eljc/article/view/v30i2p18 
|
| Author Notes: | Patrick Arras |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 27.06.2023 |
| Physical Description: | Online Resource |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/11052 |