On induced Ramsey numbers
The induced Ramsey number \(\text{IR}(G,H)\) is the smallest integer \(n\) for which there exists a graph \(F\) on \(n\) vertices such that any 2-colouring of its edges in red and blue produces either or both of a copy of a graph \(G\) induced in \(F\) with all of its edges red, or a copy of a graph \(H\) induced in \(F\) with all of its edges blue. A 2-colouring of the edges of a graph \(F\) partitions \(F\) into monochromatic subgraphs \(F_r\) and \(F_b\), containing respectively (all vertices and) all red edges and all blue edges. The weak induced Ramsey number \(\text{IR}_{\text{w}}(G,H)\) is the smallest integer \(n\) for which there exists a graph \(F\) on \(n\) vertices such that any 2-colouring of its edges in red and blue produces either or both of a copy of \(G\) induced in \(F_r\), or a copy of \(G\) induced in \(F_b\). The induced planar Ramsey number \(\text{IPR}(G,H)\) and the weak induced planar Ramsey number \(\text{IPR}_{\text{w}}(G,H)\) are defined analogously to \(\text{IR}(G,H)\) and \(\text{IR}_{\text{w}}(G,H)\), with the additional restriction that, in the 2-colouring of the edges of \(F\), \(F_r\) is planar. For any positive integer \(k\), \(kK_2\) denotes a matching consisting of \(k\) vertex-disjoint copies of \(K_2\). From the authors' introduction: ``The existence of \(\text{IR}(G,H)\) for each pair of graphs \(G\) and \(H\) was proved independently by Deuber, \textit{P. Erdős} et al.[Colloq. Math. Soc. János Bolyai 10, 585-595 (1975; Zbl 0312.05123)] and Rödl, but not much is known about the behavior of the induced Ramsey numbers, and most of the results are of asymptotic type [e.g., see \textit{I. Gorgol}, Discrete Math. 235, 159-163 (2001; Zbl 0978.05053), \textit{P. E. Haxell, Y. Kohayakawa} and \textit{T. Łuczak}, Comb. Probab. Comput. 4, 217-239 (1995; Zbl 0839.05073), \textit{Y. Kohayakawa, H. J. Prömel} and \textit{V. Rödl}, Combinatorica 18, 373-404 (1998; Zbl 0913.05074), \textit{T. Łuczak} and \textit{V. Rödl}, J. Comb. Theory, Ser. B 66, No. 2, 324-333 (1996; Zbl 0855.05084)]. Following \textit{K. Walker} [Bull. Lond. Math. Soc. 1, 187-190 (1969; Zbl 0184.27705)] and \textit{R. Steinberg} and \textit{C. A. Tovey} [J. Comb. Theory, Ser. B 59, 288-296 (1993; Zbl 0794.05091)] we consider a planar version of the induced Ramsey number, and determine its value for some pairs of graphs. In particular, we show that, in the planar case, the induced Ramsey number and its `weak' counterpart may substantially differ from each other.'' Theorem 1. For arbitrary \(k\geq 1\) and \(n\geq 2\) \(\text{IR}(kK_2,K_n)=kn\). Theorem 2. Let \(n\geq 3\). Then \(\lfloor\frac{3n}2\rfloor\leq \text{IR}(P_3,P_n)\leq 2n-1\) and \(\lfloor\frac{4n}3\rfloor\leq \text{IR}(P_3,P_n)\leq \lceil\frac{5n}3\rceil\). Theorem 3. Any planar graph \(G\) on \(n+5\) vertices, where \(n\geq 1\), contains either an induced matching \(2K_2\) or an independent set of \(n\) vertices. Theorem 4. For \(n\geq 2\) we have \(\text{IPR}_{\text{w}}(2K_2,K_n)= 2n\) for \(n\in\{2,3,4\}\) and \(n+5\) for \(n\geq 5\). Theorem 5. For \(n\geq 2\), \(\text{IPR}(2K_2,K_n)=2n\). The question is raised as to whether there exists an infinite family of graphs \(\{H_n\}_n\) such that \[ \limsup_{n\to\infty}\frac{\text{IR}(G,H_n)} {\text{IR}_{\text{w}}(G,H_n) }>1 \] for some graph \(G\).
scientific article; zbMATH DE number 1792401