Sparse anti-Ramsey graphs

DOI10.1006/JCTB.1995.1010MaRDI QIDQ1892836zbMATH OpenOpenAlexFDO

Authors Yoshiharu Kohayakawa, Tomasz Łuczak

Publication date 2 July 1995

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1995.1010

zbMATH Keywords

anti-Ramsey problemscycleedge-colouringgirthmulticoloured subgraphsrainbow subgraphsrandom graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Random graphs (graph-theoretic aspects) (05C80)

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.

Recommendations

• On an anti‐Ramsey property of Ramanujan graphs
• Rainbow subgraphs in properly edge‐colored graphs
• Ramsey-type numbers involving graphs and hypergraphs with large girth

Cited in

(8)

• On sparse graphs with given colorings and homomorphisms.
• Coloring, sparseness and girth
• Globally sparse vertex‐ramsey graphs
• On an anti‐Ramsey property of Ramanujan graphs
• Pure pairs. III. Sparse graphs with no polynomial‐sized anticomplete pairs
• Ramsey-type numbers involving graphs and hypergraphs with large girth
• Sparse sets in the complements of graphs with given girth
• Sparse Ramsey graphs

This page was built for publication: Sparse anti-Ramsey graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892836)