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

Sebastian Urbański

Discussiones Mathematicae Graph Theory (1996)

  • Volume: 16, Issue: 2, page 173-179
  • ISSN: 2083-5892

Abstract

top
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₅.

How to cite

top

Sebastian Urbański. "Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅." Discussiones Mathematicae Graph Theory 16.2 (1996): 173-179. <http://eudml.org/doc/270305>.

@article{SebastianUrbański1996,
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₅.},
author = {Sebastian Urbański},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Folkman numbers; Kₙ-free graphs; extremal graph theory; generalized Ramsey theory; extremal graph; monochromatic triangle; Ramsey property; vertex coloring},
language = {eng},
number = {2},
pages = {173-179},
title = {Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅},
url = {http://eudml.org/doc/270305},
volume = {16},
year = {1996},
}

TY - JOUR
AU - Sebastian Urbański
TI - Remarks on 15-vertex (3,3)-ramsey graphs not containing K₅
JO - Discussiones Mathematicae Graph Theory
PY - 1996
VL - 16
IS - 2
SP - 173
EP - 179
AB - 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₅.
LA - eng
KW - Folkman numbers; Kₙ-free graphs; extremal graph theory; generalized Ramsey theory; extremal graph; monochromatic triangle; Ramsey property; vertex coloring
UR - http://eudml.org/doc/270305
ER -

References

top
  1. [1] J. Bukor, A note on the Folkman number F(3,3;5), Math. Slovaca 44 (1994) 479-480. Zbl0813.05046
  2. [2] P. Erdős and A. Hajnal, Research problem 2-5, J. Combin. Theory 2 (1967) 104. 
  3. [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. Zbl0791.05039
  4. [4] J. Folkman, Graphs with monochromatic complete subgraphs in every edge coloring, SIAM J. Appl. Math. 18 (1970) 19-24, doi: 10.1137/0118004. Zbl0193.53103
  5. [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. Zbl0596.05037
  6. [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. Zbl0153.54102
  7. [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. [8] N. Hadziivanov and N. Nenov, On Graham-Spencer number, C.R. Acad. Bulg. Sci. 32 (1979) 155-158. 
  9. [9] N. Hadziivanov and N. Nenov, On Ramsey graphs, God. Sofij. Univ. Fak. Mat. Mech. 78 (1984) 211-214. 
  10. [10] N. Hadziivanov and N. Nenov, Every (3,3)-Ramsey graph without 5-cliques has more than 11 vertices, Serdica 11 (1985) 341-356. Zbl0641.05041
  11. [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. Zbl0247.05119
  12. [12] S. Lin, On Ramsey numbers and K r -coloring of graphs, J. Combin. Theory (B) 12 (1972) 82-92, doi: 10.1016/0095-8956(72)90034-2. Zbl0229.05117
  13. [13] N. Nenov, New lower bound for Graham-Spencer number, Serdica 6 (1980) 373-383. Zbl0492.05040
  14. [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. Zbl0489.05041
  15. [15] M. Schauble, Zu einem Kantenfarbungsproblem, Wiss. Z. Th. Ilemenau 15 (1969) 55-58. Zbl0205.28404
  16. [16] J. Spencer, Three hundred million points suffice, J. Combin. Theory (A) 49 (1988) 210-217. See erratum in 50 p. 323. Zbl0676.05001

NotesEmbed ?

top

You must be logged in to post comments.