On degree anti-Ramsey numbers

Shoni Gilboa, Dan Hefetz

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


The degree anti-Ramsey number ARd(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.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)31-41
عدد الصفحات11
دوريةEuropean Journal of Combinatorics
مستوى الصوت60
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 فبراير 2017

ملاحظة ببليوغرافية

Publisher Copyright:
© 2016 Elsevier Ltd


أدرس بدقة موضوعات البحث “On degree anti-Ramsey numbers'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا