Properly colored and rainbow copies of graphs with few cherries

Benny Sudakov, Jan Volec

Let G be an n-vertex graph that contains linearly many cherries (i.e., paths on 3 vertices), and let c be a coloring of the edges of the complete graph K_n such that at each vertex…