Partitioning a 2-edge-coloured graph of minimum degree $2n/3 + o(n)$ into three monochromatic cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911060734246912 |
|---|---|
| author | Allen, Peter Böttcher, Julia Lang, Richard Skokan, Jozef Stein, Maya |
| author_facet | Allen, Peter Böttcher, Julia Lang, Richard Skokan, Jozef Stein, Maya |
| contents | Lehel conjectured in the 1970s that every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomassé. However, the host graph $G$ does not have to be complete. It it suffices to require that $G$ has minimum degree at least $3n/4$, where $n$ is the order of $G$, as was shown recently by Letzter, confirming a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy. This degree condition is asymptotically tight.
Here we continue this line of research, by proving that for every red and blue edge-colouring of an $n$-vertex graph of minimum degree at least $2n/3 + o(n)$, there is a partition of the vertex set into three monochromatic cycles. This approximately verifies a conjecture of Pokrovskiy and is essentially tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_00496 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Partitioning a 2-edge-coloured graph of minimum degree $2n/3 + o(n)$ into three monochromatic cycles Allen, Peter Böttcher, Julia Lang, Richard Skokan, Jozef Stein, Maya Combinatorics Lehel conjectured in the 1970s that every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomassé. However, the host graph $G$ does not have to be complete. It it suffices to require that $G$ has minimum degree at least $3n/4$, where $n$ is the order of $G$, as was shown recently by Letzter, confirming a conjecture of Balogh, Barát, Gerbner, Gyárfás and Sárközy. This degree condition is asymptotically tight. Here we continue this line of research, by proving that for every red and blue edge-colouring of an $n$-vertex graph of minimum degree at least $2n/3 + o(n)$, there is a partition of the vertex set into three monochromatic cycles. This approximately verifies a conjecture of Pokrovskiy and is essentially tight. |
| title | Partitioning a 2-edge-coloured graph of minimum degree $2n/3 + o(n)$ into three monochromatic cycles |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2204.00496 |