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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom