Authors:
I. Gorgol
Title:
On lower bound for induced Ramsey numbers
Source:
Discussiones Mathematicae Graph Theory
Received 20.11.2017, Revised 23.04.2018, Accepted 23.04.2018, doi: 10.7151/dmgt.2151

Abstract:
We say that a graph F strongly arrows a pair of graphs (G,H) and write F \a (G,H) if any 2-coloring of its edges with red and blue leads to either a red G or a blue H appearing as induced subgraphs of F. The induced Ramsey number, \IR(G,H) is defined as \min{|V(F)|:F\a (G,H)}. We will consider two aspects of induced Ramsey numbers. Firstly we will show that the lower bound of the induced Ramsey number for a connected graph G with independence number α and a graph H with clique number ω is roughly \frac{ω2α}{2}. This bound is sharp. Moreover we will also consider the case when G is not connected providing also a sharp lower bound which is linear in both parameters.
Keywords:
induced Ramsey number

Links:
PDF