Vertex-disjoint rainbow cycles in edge-colored graphs (Q2138972)

The existence of cycles, e.g. Hamiltonian cycles or cycles of a fixed length, in graphs (and directed cycles in digraphs) is a well-studied topic, containing classic results such as Dirac's theorem. Related to this, one can also wonder about sufficient conditions for a coloured graph to have a rainbow cycle, i.e. a cycle whose vertices or edges all have different colours. The authors of this paper consider a version of a problem in this direction. Let \(G\) be an edge-colored graph of order \(n\). Then there exists a smallest function \(f(n)\) such that if every pair of vertices \((u,v)\) together see at least \(f(n)\) colours, i.e. the union of their color-neighborhood is at least \(f(n)\), then the graph \(G\) necessarily contains a rainbow cycle. In this paper, it is proved that \(f(n) \le \lfloor \frac n2 \rfloor\). The analog of this problem where one is interested in having \(k\) vertex-disjoint rainbow cycles, is also considered.