Induced Ramsey number for a star versus a fixed graph (Q2662334): Difference between revisions

Summary: We write \(F\xrightarrow{\text{ind}}(H,G)\) for graphs \(F\), \(G,\) and \(H\), if for 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\). For graphs \(G\) and \(H\), let \(\text{IR}(H,G)\) be the smallest number of vertices in a graph \(F\) such that \(F\xrightarrow{\text{ind}}(H,G)\). In this note we consider the case when \(G\) is a star on \(n\) edges, for large \(n\) and \(H\) is a fixed graph. We prove that \[(\chi(H)-1) n \leqslant \text{IR}(H, K_{1,n}) \leqslant (\chi(H)-1)^2n + \epsilon n,\] for any \(\epsilon>0\), sufficiently large \(n\), and \(\chi(H)\) 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 when \(H\) is a clique.