Premium
Rainbow subgraphs in properly edge‐colored graphs
Author(s) -
Rödl Vojtech,
Tuza Zsolt
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030207
Subject(s) - rainbow , monochromatic color , colored , combinatorics , edge coloring , enhanced data rates for gsm evolution , mathematics , discrete mathematics , computer science , physics , graph , telecommunications , optics , line graph , materials science , graph power , composite material
We prove that there exist graphs G with arbitrarily large girth such that every proper edge coloring of G contains a rainbow cycle (i.e., a cycle having no pair of monochromatic edges). This answers a problem raised by J. Spencer more than 10 years ago.