Geodesic
A Note on Lower Bounds for Induced Ramsey Numbers
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 647-654

Voir la notice de l'article provenant de la source Library of Science

We say that a graph F strongly arrows a pair of graphs (G,H) and write F (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 (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 ω^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 
@article{DMGT_2019_39_3_a2,
     author = {Gorgol, Izolda},
     title = {A {Note} on {Lower} {Bounds} for {Induced} {Ramsey} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {647--654},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a2/}
}
TY  - JOUR
AU  - Gorgol, Izolda
TI  - A Note on Lower Bounds for Induced Ramsey Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 647
EP  - 654
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a2/
LA  - en
ID  - DMGT_2019_39_3_a2
ER  - 
%0 Journal Article
%A Gorgol, Izolda
%T A Note on Lower Bounds for Induced Ramsey Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 647-654
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a2/
%G en
%F DMGT_2019_39_3_a2
Gorgol, Izolda. A Note on Lower Bounds for Induced Ramsey Numbers. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 647-654. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a2/