Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918044980215808 |
|---|---|
| author | Benevides, Fabrício Siqueira Quintino, Arthur Lima Talon, Alexandre |
| author_facet | Benevides, Fabrício Siqueira Quintino, Arthur Lima Talon, Alexandre |
| contents | Given an $r$-edge-colouring of the edges of a graph $G$, we say that it can be partitioned into $p$ monochromatic cycles when there exists a set of $p$ vertex-disjoint monochromatic cycles covering all the vertices of $G$. In the literature of this problem, an edge and a single vertex both count as a cycle.
We show that for every $2$-colouring of the edges of a complete balanced bipartite graph, $K_{n,n}$, it can be partitioned into at most 4 monochromatic cycles. This type of question was first studied in 1970 for complete graphs and in 1983, by Gyárfás and Lehel, for $K_{n,n}$. In 2014, Pokrovskiy showed for all $n$ that, given any $2$-colouring of its edges, $K_{n,n}$ can be partitioned into at most three monochromatic paths. It turns out that finding monochromatic cycles instead of paths is a natural question that has also been raised for other graphs. In 2015, Schaudt and Stein showed that 14 cycles are sufficient for sufficiently large $2$-edge-coloured $K_{n,n}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_03394 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles Benevides, Fabrício Siqueira Quintino, Arthur Lima Talon, Alexandre Combinatorics Discrete Mathematics 05C15, 05C35, 05C70 G.2.2 Given an $r$-edge-colouring of the edges of a graph $G$, we say that it can be partitioned into $p$ monochromatic cycles when there exists a set of $p$ vertex-disjoint monochromatic cycles covering all the vertices of $G$. In the literature of this problem, an edge and a single vertex both count as a cycle. We show that for every $2$-colouring of the edges of a complete balanced bipartite graph, $K_{n,n}$, it can be partitioned into at most 4 monochromatic cycles. This type of question was first studied in 1970 for complete graphs and in 1983, by Gyárfás and Lehel, for $K_{n,n}$. In 2014, Pokrovskiy showed for all $n$ that, given any $2$-colouring of its edges, $K_{n,n}$ can be partitioned into at most three monochromatic paths. It turns out that finding monochromatic cycles instead of paths is a natural question that has also been raised for other graphs. In 2015, Schaudt and Stein showed that 14 cycles are sufficient for sufficiently large $2$-edge-coloured $K_{n,n}$. |
| title | Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles |
| topic | Combinatorics Discrete Mathematics 05C15, 05C35, 05C70 G.2.2 |
| url | https://arxiv.org/abs/2409.03394 |