Premium
On an anti‐Ramsey threshold for sparse graphs with one triangle
Author(s) -
Kohayakawa Y.,
Konstadinidis P. B.,
Mota G. O.
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22150
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , triangle free graph , 1 planar graph , chordal graph
For graphs G and H , let G → p rb H denote the property that for every proper edge‐coloring of G (with an arbitrary number of colors) there is a rainbow copy of H in G , that is, a copy of H with no two edges of the same color. The authors (2014) proved that, for every graph H , the threshold function p H rb = p H rb( n )of this property for the binomial random graph G ( n , p ) is asymptotically at most n − 1 / m ( 2 )( H ), wherem ( 2 )( H )denotes the so‐called maximum 2‐density of H . Nenadov et al. (2014) proved that if H is a cycle with at least seven vertices or a complete graph with at least 19 vertices, thenp H rb = n − 1 / m ( 2 )( H ). We show that there exists a fairly rich, infinite family of graphs F containing a triangle such that if p ≥ D n − βfor suitable constants D = D ( F ) > 0 and β = β ( F ) , where β > 1 / m ( 2 )( F ) , then G ( n , p ) → p rb F almost surely. In particular,p F rb ≪ n − 1 / m ( 2 )( F )for any such graph F .