pith. sign in

arxiv: 1507.07381 · v1 · pith:TU73A4WMnew · submitted 2015-07-27 · 🧮 math.CO

On degree anti-Ramsey numbers

classification 🧮 math.CO
keywords degreeanti-ramseynumbersboundgraphnumberproveupper
0
0 comments X
read the original abstract

The degree anti-Ramsey number $AR_d(H)$ 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$. 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 $2$. Our proofs involve a variety of tools, including a classical result of Bollob\'as concerning cross intersecting families and a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.