A subgraph of an edge-coloured graph is called rainbow if all its edges havedifferent colours. The problem of finding rainbow subgraphs goes back to thework of Euler on transversals in Latin squares and was extensively studiedsince then. In this paper we consider two related questions concerning rainbowsubgraphs of complete, edge-coloured graphs and digraphs. In the first part, weshow that every properly edge-coloured complete directed graph contains adirected rainbow cycle of length $n-O(n^{4/5})$. This is motivated by an oldproblem of Hahn and improves a result of Gyarfas and Sarkozy. In the secondpart, we show that any tree $T$ on $n$ vertices with maximum degree$Delta_Tleq eta n/log n$ has a rainbow embedding into a properlyedge-coloured $K_n$ provided that every colour appears at most $lpha n$ timesand $lpha, eta$ are sufficiently small constants.
展开▼
机译：如果所有边缘都有颜色，则边缘彩色图形的子图称为彩虹。找到彩虹子图的问题返回拉丁广场横向横向的欧拉的主题，并广泛研究了。在本文中，我们考虑了有关完整，边缘彩色的图形和上色的雨棚和上色的两个相关问题。在第一部分中，Wealow，每一个正确的边缘彩色的完整定向图都包含长度$ N-O的彩虹循环（n ^ {4/5}）$。这是由哈恩的旧物业的动机，并改善了甘草和萨科齐的结果。在第二个，我们展示了任何树$ T $的$ N $顶点具有最大程度的$ delta_t leq beta n / log n $的彩虹嵌入到正确的彩色$ k_n $的rainbow edits至多$ alpha n $ timesand $ alpha， beta $是足够的小常数。
展开▼
