Sparse anti-Ramsey graphs (Q1892836)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sparse anti-Ramsey graphs |
scientific article |
Statements
Sparse anti-Ramsey graphs (English)
0 references
2 July 1995
0 references
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.
0 references
anti-Ramsey problems
0 references
multicoloured subgraphs
0 references
rainbow subgraphs
0 references
girth
0 references
edge-colouring
0 references
cycle
0 references
random graphs
0 references