Geodesic
A Note on Upper Bounds for Some Generalized Folkman Numbers
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 939-950.

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

We present some new constructive upper bounds based on product graphs for generalized vertex Folkman numbers. They lead to new upper bounds for some special cases of generalized edge Folkman numbers, including the cases Fe(K3, K4 − e; K5) ≤ 27 and Fe(K4 − e, K4 − e; K5) ≤ 51. The latter bound follows from a construction of a K5-free graph on 51 vertices, for which every edge coloring with two colors contains a monochromatic K4 − e.
Keywords: Folkman number, Ramsey number 
@article{DMGT_2019_39_4_a13,
     author = {Xu, Xiaodong and Liang, Meilian and Radziszowski, Stanis{\l}aw},
     title = {A {Note} on {Upper} {Bounds} for {Some} {Generalized} {Folkman} {Numbers}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {939--950},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a13/}
}
TY  - JOUR
AU  - Xu, Xiaodong
AU  - Liang, Meilian
AU  - Radziszowski, Stanisław
TI  - A Note on Upper Bounds for Some Generalized Folkman Numbers
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 939
EP  - 950
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a13/
LA  - en
ID  - DMGT_2019_39_4_a13
ER  - 
%0 Journal Article
%A Xu, Xiaodong
%A Liang, Meilian
%A Radziszowski, Stanisław
%T A Note on Upper Bounds for Some Generalized Folkman Numbers
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 939-950
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a13/
%G en
%F DMGT_2019_39_4_a13
Xu, Xiaodong; Liang, Meilian; Radziszowski, Stanisław. A Note on Upper Bounds for Some Generalized Folkman Numbers. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 939-950. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a13/

[1] A. Bikov and N. Nenov, The edge Folkman number Fe (3, 3; 4) is greater than 19, Geombinatorics XXVII (2017) 5–14.

[2] A. Dudek, T. Retter and V. Rödl, On generalized Ramsey numbers of Erdős and Rogers, J. Combin. Theory Ser. B 109 (2014) 213–227. doi:10.1016/j.jctb.2014.06.006

[3] J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970) 19–24. doi:10.1137/0118004

[4] R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey Theory (John Wiley & Sons, 1990).

[5] N. Kolev, A multiplicative inequality for vertex Folkman numbers, Discrete Math. 308 (2008) 4263–4266. doi:10.1016/j.disc.2007.08.008

[6] Y. Li and Q. Lin, On generalized Folkman numbers, Taiwanese J. Math. 21 (2017) 1–9. doi:10.11650/tjm.21.2017.7710

[7] Q. Lin and Y. Li, A Folkman linear family, SIAM J. Discrete Math. 29 (2015) 1988–1998. doi:10.1137/130947647

[8] N. Nenov, An example of a 15 -vertex (3, 3) -Ramsey graph with clique number 4, C.R. Acad. Bulgare Sci. 34 (1981) 1487–1489, in Russian.

[9] J. Nešetřil and V. Rödl, The Ramsey property for graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20 (1976) 243–249. doi:10.1016/0095-8956(76)90015-0

[10] K. Piwakowski, S. Radziszowski and S. Urbański, Computation of the Folkman number Fe (3, 3; 5), J. Graph Theory 32 (1999) 41–49. doi:10.1002/(SICI)1097-0118(199909)32:1(41::AID-JGT4)3.0.CO;2-P

[11] V. Rödl, A. Ruciński and M. Schacht, An exponential-type upper bound for Folkman numbers, Combinatorica 30 (2017) 767–784. doi:10.1007/s00493-015-3298-1

[12] X. Xu, M. Liang and S. Radziszowski, Chromatic vertex Folkman numbers, (2018) preprint. arXiv 1612.08136

[13] X. Xu, M. Liang and S. Radziszowski, On the nonexistence of some generalized Folkman numbers, Graphs Combin., to appear. arXiv 1705.06268

[14] X. Xu, H. Luo and Z. Shao, Upper and lower bounds for Fv (4, 4; 5), Electron. J. Combin. (2010) 17 #N34.

[15] X. Xu and Z. Shao, On the lower bound for Fv ( k, k ; k + 1) and Fe (3, 4; 5), Util. Math. 81 (2010) 187–192.

[16] X. Xu, H. Luo, W. Su and K. Wu, On the upper bounds for vertex Folkman numbers, Guangxi Sci. 15 (2008) 211–215.