Anti-Ramsey Threshold of Cycles for Sparse Graphs
Author(s) -
Gabriel F. Barros,
Bruno Pasqualotto Cavalar,
Guilherme Oliveira Mota,
Olaf Parczyk
Publication year - 2019
Publication title -
electronic notes in theoretical computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.242
H-Index - 60
ISSN - 1571-0661
DOI - 10.1016/j.entcs.2019.08.009
Subject(s) - mathematics , combinatorics , computer science , discrete mathematics
For graphs G and H, let G ⟶ p rb H denote the property that for every proper edge colouring of G there is a rainbow copy of H in G. Extending a result of Nenadov, Person, Skoric and Steger (2017), we prove that n−1/m2(Cl) is the threshold for G ( n , p ) ⟶ p rb C l when l ≥ 5. Thus our result together with a result of the third author which says that the threshold for G ⟶ p rb C 4 is n−3/4 settles the problem of determining the threshold for G ⟶ p rb C l for all values of l.
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