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/

[1] J. Beck, On the size Ramsey number of paths, trees and circuits I, J. Graph Theory 7 (1983) 115–129. doi:10.1002/jgt.3190070115

[2] D. Conlon, J. Fox and B. Sudakov, On two problems in graph Ramsey theory, Combinatorica 32 (2012) 513–535. doi:10.1007/s00493-012-2710-3

[3] V. Chvátal and F. Harary, Generalized Ramsey theory for graphs. III. Small off-diagonal numbers, Pacific J. Math. 41 (1972) 335–345. doi:10.2140/pjm.1972.41.335

[4] V. Chvátal, Tree-complete graph Ramsey numbers, J. Graph Theory 1 (1977) 93. doi:10.1002/jgt.3190010118

[5] W. Deuber, A generalization of Ramsey’s theorem, in: Infinite and Finite Sets, R. Rado A. Hajnal and V. Sós, (Eds.) 10 (North-Holland, Amsterdam, 1975) 323–332.

[6] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947) 292–294 doi:10.1090/S0002-9904-1947-08785-1

[7] P. Erdős, On some problems in graph theory, combinatorial analysis and combinatorial number theory, in: Proc. Conf. Hon. P. Erdös, Cambridge 1983, Graph Theory and Combinatorics (Academic Press, New York, 1984) 1–17.

[8] P. Erdős, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, in: Infinite and Finite Sets, R. Rado A. Hajnal and V. Sós, (Eds.) 10 (North-Holland, 1975) 585–595.

[9] I. Gorgol, A note on a triangle-free-complete graph induced Ramsey number, Discrete Math. 235 (2001) 159–163. doi:10.1016/S0012-365X(00)00269-7

[10] I. Gorgol and T. Luczak, On induced Ramsey numbers, Discrete Math. 251 (2002) 87–96. doi:10.1016/S0012-365X(01)00328-4

[11] F. Harary, J. Nešetřil and V. Rödl, Generalized Ramsey theory for graphs. XIV. Induced Ramsey numbers, in: Proceedings of the Third Czechoslovak Symposium on Graph Theory, Praque 1982, Graphs and Other Combinatorial Topics 59 (1983) 90–100.

[12] P. Haxell, Y. Kohayakawa and T. Luczak, The induced size-Ramsey number of cycles, Combin. Probab. Comput. 4 (1995) 217–239. doi:10.1017/S0963548300001619

[13] Y. Kohayakawa, H.J. Prömel and V. Rödl, Induced Ramsey numbers, Combinatorica 18 (1998) 373–404. doi:10.10071PL00009828

[14] A. Kostochka and N. Sheikh, On the induced Ramsey number IR ( P 3, H ), Topics in Discrete Mathematics 26 (2006) 155–167. doi:10.1007/3-540-33700-8_10

[15] T. Luczak and V. Rödl, On induced Ramsey numbers for graphs with bounded maximum degree, J. Combin. Theory Ser. B 66 (1996) 324–333. doi:10.1006/jctb.1996.0025

[16] V. Rödl, The Dimention of a Graph and Generalized Ramsey Theorems, Master’s Thesis (Charles University, Prague, 1973).

[17] V. Rödl, A generalization of Ramsey theorem, in: Proc. Symp. Comb. Anal., Zielona Góra 1976, Graphs, Hypergraphs and Block Systems (1976) 211–219.

[18] M. Schaefer and P. Shah, Induced graph Ramsey theory, Ars Combin. 66 (2003) 3–21.