Long directed rainbow cycles and rainbow spanning trees (Q2189824): Difference between revisions

The first theorem in this paper is that every properly edge-coloured complete directed graph contains a directed rainbow cycle of length \(n-O(n^{4/5})\) and a rainbow forest of paths of total length \(n-O(n^{2/3})\). This improves and generalises a result of \textit{A. Gyárfás} and \textit{G. N. Sárközy} [Discrete Math. 327, 96--102 (2014; Zbl 1288.05087)]. The second main result of the paper is that there exist positive constants \(\alpha\), \(\beta\) so that the following holds for every integer \(n\). Let \(T\) be a tree on \(n\) vertices with maximum degree at most \(\beta n / \log n\). Then every proper colouring of \(K_n\), in which no colour occurs on more than \(\alpha n\) edges, contains a rainbow copy of \(T\). The authors note that this result is false for \(\alpha=1\) but conjecture that it might be true for any \(\alpha<1/2\).