On degree anti-Ramsey numbers. (February 2017)

• Record Type: Journal Article
• Authors: Gilboa, Shoni; Hefetz, Dan
• Is Part Of: European journal of combinatorics. Volume 60(2017)
• Page Start: 31
• Page End: 41
• Publication Date: 2017-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2016.09.002
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: The degree anti-Ramsey number A R 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ás concerning cross intersecting families and a topological version of Hall's Theorem due to Aharoni, Berger and Meshulam.