کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651913 1632582 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Properly colored and rainbow copies of graphs with few cherries
ترجمه فارسی عنوان
نسخه های رنگی و رنگین کمان از گراف ها با گیلاس چند؟
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Let G be an n-vertex graph that contains linearly many cherries (i.e., paths on 3 vertices), and let c be a coloring of the edges of the complete graph Kn such that at each vertex every color appears only constantly many times. In 1979, Shearer conjectured that such a coloring c must contain a properly colored copy of G. We prove this conjecture even for graphs G with O(n4/3) cherries and show that this is up to a constant factor best possible. We also prove an analogue of this conjecture for colorings of E(Kn) where for each color the total number of appearances is bounded, and then the aim is to find a rainbow copy of G.Our proofs combine a framework of Lu and Székely for using lopsided Lovász local lemma in the space of random injections together with some other ideas.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 315-321