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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 פבר׳ 2017

הערה ביבליוגרפית

Publisher Copyright:
© 2016 Elsevier Ltd

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On degree anti-Ramsey numbers'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי