Degree anti-Ramsey numbers

The degree anti-Ramsey number of a graph H is the smallest integer k for which there exists a graph G with maximum degree at most k such that any proper edge colouring of G yields a rainbow copy of H (i.e., all edges of this copy of H have distinct colours).

We determine the degree anti-Ramsey number of any tree, and then extend this to any forest using a classical result of Bollobas concerning cross intersecting families. We also use a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam to get an upper bound (which is best possible up to a factor of 2) on the degree anti-Ramsey numbers of cycles of any length, .

Joint work with Danny Hefetz.