On induced Ramsey numbers
type: Item
instance of: scholarly article
title: On induced Ramsey numbers
zbMATH Open document ID: 1004.05042
DOI: 10.1016/S0012-365X(01)00328-4
author: Izolda Gorgol
author: Tomasz Łuczak
published in: Discrete Mathematics
publication date: 2002-08-29T00:00:00Z
review text: 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, …
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1792401
reviewed by: William G. Brown
MaRDI profile type: Publication
Recommended article: Planar Ramsey Numbers
Recommended article: Some modifications of Ramsey numbers
Recommended article: On induced Ramsey numbers for graphs with bounded maximum degree
Recommended article: A note on lower bounds for induced Ramsey numbers
Recommended article: Induced Ramsey numbers
Recommended article: Q3378337
Recommended article: The planar Ramsey number \(PR(K_4-e,K_5\))
Recommended article: A note on a triangle-free -- complete graph induced Ramsey number
Recommended article: Q3331250
Recommended article: The planar Ramsey number for \(C_4\) and \(K_5\) is 13
description: scientific article; zbMATH DE number 1792401