Sparse anti-Ramsey graphs
type: Item
instance of: scholarly article
title: Sparse anti-Ramsey graphs
zbMATH Open document ID: 0820.05048
author: Yoshiharu Kohayakawa
author: Tomasz Łuczak
published in: Journal of Combinatorial Theory. Series B
publication date: 1995-07-02T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 767685
zbMATH Keywords: anti-Ramsey problems
zbMATH Keywords: multicoloured subgraphs
zbMATH Keywords: rainbow subgraphs
zbMATH Keywords: girth
zbMATH Keywords: edge-colouring
zbMATH Keywords: cycle
zbMATH Keywords: random graphs
MaRDI profile type: Publication
full work available at URL: jctb.1995.1010
OpenAlex ID: W2095105201
DOI: 10.1006/JCTB.1995.1010
description: scientific article; zbMATH DE number 767685