Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653179 | European Journal of Combinatorics | 2017 | 11 Pages |
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
Shoni Gilboa, Dan Hefetz,