DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 16(2) (1996) 173-179
DOI: https://doi.org/10.7151/dmgt.1032

REMARKS ON 15-VERTEX (3,3)-RAMSEY GRAPHS NOT CONTAINING K5

Sebastian Urbański

Department of Discrete Mathematics
Faculty of Mathematics and Computer Science
Adam Mickiewicz University Poznań, Poland

Abstract

The paper gives an account of previous and recent attempts to determine the order of a smallest graph not containing K5 and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K4-free graph with the same Ramsey property in the vertex coloring case is found. This yields a new construction of one of the only two known 15-vertex (3,3)-Ramsey graphs not containing K5.

Keywords: Folkman numbers, Kn-free graphs, extremal graph theory, generalized Ramsey theory.

1991 Mathematics Subject Classification: 05C55, 05C35.

References

[1] J. Bukor, A note on the Folkman number F(3,3;5), Math. Slovaca 44 (1994) 479-480.
[2] P. Erdős and A. Hajnal, Research problem 2-5, J. Combin. Theory 2 (1967) 104.
[3] M. Erickson, An upper bound for the Folkman number F(3,3;5), J. Graph Theory 17 (1993) 679-681, doi: 10.1002/jgt.3190170604.
[4] J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970) 19-24, doi: 10.1137/0118004.
[5] P. Frankl and V. Rödl, Large triangle-free subgraphs in graphs without K4, Graphs and Combinatorics 2 (1986) 135-144, doi: 10.1007/BF01788087.
[6] R.L. Graham, On edgewise 2-colored graphs with monochromatic triangles and containing no complete hexagon, J. Combin. Theory 4 (1968) 300, doi: 10.1016/S0021-9800(68)80009-2.
[7] R.L. Graham and J.H. Spencer, On small graphs with forced monochromatic triangles, in: Recent Trends in Graph Theory. Lecture Notes in Math. 186 (Springer-Verlag, Berlin, 1971) 137-141, doi: 10.1007/BFb0059431.
[8] N. Hadziivanov and N. Nenov, On Graham-Spencer number, C.R. Acad. Bulg. Sci. 32 (1979) 155-158.
[9] N. Hadziivanov and N. Nenov, On Ramsey graphs, God. Sofij. Univ. Fak. Mat. Mech. 78 (1984) 211-214.
[10] N. Hadziivanov and N. Nenov, Every (3,3)-Ramsey graph without 5-cliques has more than 11 vertices, Serdica 11 (1985) 341-356.
[11] R.W. Irving, On a bound of Graham and Spencer for graph-coloring constant, J. Combin. Theory 15 (1973) 200-203, doi: 10.1016/0095-8956(73)90021-X.
[12] S. Lin, On Ramsey numbers and Kr-coloring of graphs, J. Combin. Theory (B) 12 (1972) 82-92, doi: 10.1016/0095-8956(72)90034-2.
[13] N. Nenov, New lower bound for Graham-Spencer number, Serdica 6 (1980) 373-383.
[14] N. Nenov, An example of 15-vertex (3,3)-Ramsey graph with the clique number 4, C.R. Acad. Bulg. Sci. 34 (1981) 1487-1489.
[15] M. Schauble, Zu einem Kantenfarbungsproblem, Wiss. Z. Th. Ilemenau 15 (1969) 55-58.
[16] J. Spencer, Three hundred million points suffice, J. Combin. Theory (A) 49 (1988) 210-217. See erratum in 50 p. 323.
Close