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: |