Monochromatic partitions in 2-edge-coloured bipartite graphs
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_ | 1866913271836049408 |
|---|---|
| author | Fernández, Camila Pavez-Signé, Matías Stein, Maya |
| author_facet | Fernández, Camila Pavez-Signé, Matías Stein, Maya |
| contents | We study two variations of the Gyarfas--Lehel conjecture on the minimum number of monochromatic components needed to cover an edge-coloured complete bipartite graph. Specifically, we show the following. - For p>> (\log n/n)^{1/2}, w.h.p.~every 2-colouring of the random bipartite graph G~ G(n,n,p) admits a cover of all but O(1/p) vertices of G using at most three vertex-disjoint monochromatic components. - For every 2-colouring of a bipartite graph G with parts of size n and minimum degree (13/16+o(1))n, the vertices of G can be covered using at most three vertex-disjoint monochromatic components. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12587 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Monochromatic partitions in 2-edge-coloured bipartite graphs Fernández, Camila Pavez-Signé, Matías Stein, Maya Combinatorics We study two variations of the Gyarfas--Lehel conjecture on the minimum number of monochromatic components needed to cover an edge-coloured complete bipartite graph. Specifically, we show the following. - For p>> (\log n/n)^{1/2}, w.h.p.~every 2-colouring of the random bipartite graph G~ G(n,n,p) admits a cover of all but O(1/p) vertices of G using at most three vertex-disjoint monochromatic components. - For every 2-colouring of a bipartite graph G with parts of size n and minimum degree (13/16+o(1))n, the vertices of G can be covered using at most three vertex-disjoint monochromatic components. |
| title | Monochromatic partitions in 2-edge-coloured bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.12587 |