Properly colored and rainbow copies of graphs with few cherries
Properly colored and rainbow copies of graphs with few cherries
复制标题
带有少量樱桃的图表的正确彩色和彩虹副本
DOI：
10.1016/j.jctb.2016.07.001
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Jan Volec
中科院分区：
文献类型：
--
作者：
B. Sudakov;Jan Volec
设G是一个有n个顶点的图，它包含线性多的樱桃（即3个顶点上的路径），设c是完整图K n的边的着色，这样在每个顶点上每种颜色只出现多次。1979年，Shearer推测这样的着色c必须包含G的适当着色副本。我们以强形式建立了这个猜想，证明它甚至对含有O （n 4/3）个樱桃的图G成立，而且这个关于樱桃数量的界是最大可能的，直到一个常数因子。我们也证明了在K n的每一个边着色中都可以找到这样的G的彩虹副本，其中所有颜色都出现有限次。我们的证明结合了Lu和szsamkely的框架，用于在随机双射空间中使用不平衡Lovász局部引理以及一些附加的想法。
Let G be an n-vertex graph that contains linearly many cherries (ie, paths on 3 vertices), and let c be a coloring of the edges of the complete graph K n 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 establish this conjecture in a strong form, showing that it holds even for graphs G with O (n 4/3) cherries and moreover this bound on the number of cherries is best possible up to a constant factor. We also prove that one can find a rainbow copy of such G in every edge-coloring of K n in which all colors appear bounded number of times. Our proofs combine a framework of Lu and Székely for using the lopsided Lovász local lemma in the space of random bijections together with some additional ideas.