Sparse anti-Ramsey graphs (Q1892836)

It is shown that for every \(\ell \geq 3\) there exists a graph \(G\) of girth \(\ell\) such that in any proper edge-colouring of \(G\) one may find a cycle of length \(\ell\) all of whose edges are given different colours. This result settles a particular case of a conjecture of Rödl and Tuza [\textit{V. Rödl} and \textit{Zs. Tuza}, Rainbow subgraphs in properly edge- coloured graphs, Random Struct. Algorithms 3, No. 2, 175-182 (1992; Zbl 0754.05039)]. The proof relies heavily on the use of random graphs and is therefore nonconstructive. This result improves on previous constructive results of Haxell and Kohayakawa.