Article ID Journal Published Year Pages File Type
4653179 European Journal of Combinatorics 2017 11 Pages PDF
Abstract

The degree anti-Ramsey number ARd(H)ARd(H) of a graph HH is the smallest integer kk for which there exists a graph GG with maximum degree at most kk such that any proper edge colouring of GG yields a rainbow copy of HH. In this paper we prove a general upper bound on degree anti-Ramsey numbers, determine the precise value of the degree anti-Ramsey number of any forest, and prove an upper bound on the degree anti-Ramsey numbers of cycles of any length which is best possible up to a multiplicative factor of 22. Our proofs involve a variety of tools, including a classical result of Bollobás concerning cross intersecting families and a topological version of Hall’s Theorem due to Aharoni, Berger and Meshulam.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,