论文标题
诱发恒星与固定图的Ramsey编号
Induced Ramsey number for a star versus a fixed graph
论文作者
论文摘要
对于图G和H，让诱导的Ramsey编号IR（H，G）是图F中最小数量的顶点，使得F中F的任何颜色为红色和蓝色的边缘，h或blue的红色诱导副本或G的蓝色诱导副本是G。在此注释中，当G = SN是N Edges上的情况时，我们考虑了N Edges上的n edges，而H e则为N，并且H是固定的。我们证明（R-1）n <ir（h，sn）<（r-1）（r-1）n + cn，对于任何c> 0，足够大的n，以及表示h的变色数的r。下限对于任何固定的双方HE都渐近地紧密。
For graphs G and H, let the induced Ramsey number IR(H,G) be the smallest number of vertices in a graph F such that any coloring of the edges of F in red and blue, there is either a red induced copy of H or a blue induced copy of G. In this note we consider the case when G=Sn is a star on n edges, for large n, and H is a fixed graph. We prove that (r-1)n < IR(H, Sn) < (r-1)(r-1)n + cn, for any c>0, sufficiently large n, and r denoting the chromatic number of H. The lower bound is asymptotically tight for any fixed bipartite H. The upper bound is attained up to a constant factor, for example by a clique H.
