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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.