Finding large rainbow trees in colourings of \(K_{n, n}\)

Julian Matthes¹

¹Alfred-Weber-Institut für Wirtschaftswissenschaften, Ruprecht-Karls-Universität Heidelberg

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

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 $K_{2n+1}$ contains a rainbow copy of any tree with $n$ edges, thereby resolving a long-standing conjecture by Ringel: For large $n$, $K_{2n+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 $K_{n,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 $K_{n+o(1),n+o(1)}$. We conjecture that for large $n$, $K_{n,n}$ can be decomposed into $n$ copies of any tree with $n$ edges.

Détail

DOI : 10.37236/10976

Classification : 05C70, 05C05, 05B40
Mots-clés : rainbow, edge-colouring