Finding large rainbow trees in colourings of Kn,n
A subgraph of an edge-coloured graph is called rainbow if all of its edges have distinct colours. An edge-colouring is called locally k-bounded if each vertex is incident with at most k edges of the same colour. Recently, Montgomery, Pokrovskiy and Sudakov showed that for large n, a certain locally...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
Nov 17, 2023
|
| In: |
The electronic journal of combinatorics
Year: 2023, Volume: 30, Issue: 4, Pages: 1-21 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/10976 |
| Online Access: | Verlag, kostenfrei, Volltext: https://doi.org/10.37236/10976 Verlag, kostenfrei, Volltext: https://www.webofscience.com/api/gateway?GWVersion=2&SrcAuth=DynamicDOIArticle&SrcApp=WOS&KeyAID=10.37236%2F10976&DestApp=DOI&SrcAppSID=EUW1ED0B7AFst6dUktUywCjS437yp&SrcJTitle=ELECTRONIC+JOURNAL+OF+COMBINATORICS&DestDOIRegistrantName=The+Electronic+Journal+of+Combinatorics 
|
| Author Notes: | Julian Matthes |
| Summary: | A subgraph of an edge-coloured graph is called rainbow if all of its edges have distinct colours. An edge-colouring is called locally k-bounded if each vertex is incident with at most k edges of the same colour. Recently, Montgomery, Pokrovskiy and Sudakov showed that for large n, a certain locally 2-bounded edge-colouring of the complete graph K2n+1 contains a rainbow copy of any tree with n edges, thereby resolving a long-standing conjecture by Ringel: For large n, K2n+1 can be decomposed into copies of any tree with n edges. In this paper, we employ their methods to show that any locally k-bounded edge-colouring of the complete bipartite graph Kn,n contains a rainbow copy of any tree T with (1 - o(1))n/k edges. We show that this implies that every tree with n edges packs at least n times into Kn+o(1),n+o(1). We conjecture that for large n, Kn,n can be decomposed into n copies of any tree with n edges. |
|---|---|
| Item Description: | Im Titel sind beide n tiefgestellt Gesehen am 22.01.2024 |
| Physical Description: | Online Resource |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/10976 |