Geodesic
Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
Patrick Arras1
1Universität Heidelberg, Institut für Informatik
The electronic journal of combinatorics, Tome 30 (2023) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/11052
Classification : 05C70, 05C15, 05C38, 05D10
Mots-clés : Ore-type condition, local \(r\)-edge-colourings

Patrick Arras  1

1 Universität Heidelberg, Institut für Informatik 
@article{10_37236_11052,
     author = {Patrick Arras},
     title = {Ore- and {P\'osa-type} conditions for partitioning 2-edge-coloured graphs into monochromatic cycles},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {2},
     doi = {10.37236/11052},
     zbl = {1514.05126},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11052/}
}
TY  - JOUR
AU  - Patrick Arras
TI  - Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11052/
DO  - 10.37236/11052
ID  - 10_37236_11052
ER  - 
%0 Journal Article
%A Patrick Arras
%T Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11052/
%R 10.37236/11052
%F 10_37236_11052
Patrick Arras. Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11052

Cité par Sources :