کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651913 | 1632582 | 2015 | 7 صفحه PDF | دانلود رایگان |
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.
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 315-321