Download PDF - Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅All rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅

Authors 1

Affiliations

  1. 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 K₅ and such that every 2-coloring of its edges results in a monochromatic triangle. A new 14-vertex K₄-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 K₅.

Keywords

ENG
Folkman numbers, Kₙ-free graphs, extremal graph theory, generalized Ramsey theory

Bibliography

  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 K₄, 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.
Discussiones Mathematicae Graph Theory
1996/16/2
Export to PBN, Opens in new tab
Pages:
173-179
Main language of publication
English
Received
1996-07-27
Accepted
1996-11-18
Published
1996
Exact and natural sciences