Planar Ramsey numbers

Izolda Gorgol

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 1-2, page 45-50
  • ISSN: 2083-5892

Abstract

top
The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.

How to cite

top

Izolda Gorgol. "Planar Ramsey numbers." Discussiones Mathematicae Graph Theory 25.1-2 (2005): 45-50. <http://eudml.org/doc/270703>.

@article{IzoldaGorgol2005,
abstract = {The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.},
author = {Izolda Gorgol},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Ramsey number; planar graph; induced subgraph},
language = {eng},
number = {1-2},
pages = {45-50},
title = {Planar Ramsey numbers},
url = {http://eudml.org/doc/270703},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Izolda Gorgol
TI - Planar Ramsey numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 1-2
SP - 45
EP - 50
AB - The planar Ramsey number PR(G,H) is defined as the smallest integer n for which any 2-colouring of edges of Kₙ with red and blue, where red edges induce a planar graph, leads to either a red copy of G, or a blue H. In this note we study the weak induced version of the planar Ramsey number in the case when the second graph is complete.
LA - eng
KW - Ramsey number; planar graph; induced subgraph
UR - http://eudml.org/doc/270703
ER -

References

top
  1. [1] K. Appel and W. Haken, Every planar map is four colourable. Part I. Discharging, Illinois J. Math. 21 (1977) 429-490. Zbl0387.05009
  2. [2] K. Appel, W. Haken, and J. Koch, Every planar map is four colourable. Part II. Reducibility, Illinois J. Math. 21 (1977) 491-567. Zbl0387.05010
  3. [3] W. Deuber, A generalization of Ramsey's theorem, in: R. Rado, A. Hajnal and V. Sós, eds., Infinite and finite sets, vol. 10 (North-Holland, 1975) 323-332. 
  4. [4] P. Erdős, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, in: R. Rado, A. Hajnal and V. Sós, eds., Infinite and finite sets, vol. 10 (North-Holland, 1975) 585-595. Zbl0312.05123
  5. [5] I. Gorgol, A note on a triangle-free - complete graph induced Ramsey number, Discrete Math. 235 (2001) 159-163, doi: 10.1016/S0012-365X(00)00269-7. Zbl0978.05053
  6. [6] I. Gorgol, Planar and induced Ramsey numbers (Ph.D. thesis (in Polish), Adam Mickiewicz University Poznań, Poland, 2000) 51-57. 
  7. [7] I. Gorgol and T. Łuczak, On induced Ramsey numbers, Discrete Math. 251 (2002) 87-96, doi: 10.1016/S0012-365X(01)00328-4. Zbl1004.05042
  8. [8] R.E. Greenwood and A.M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math. 7 (1955) 1-7, doi: 10.4153/CJM-1955-001-4. Zbl0064.17901
  9. [9] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. Natur. Reihe 8 (1958/1959) 109-120. 
  10. [10] B. Grünbaum, Grötzsch's theorem on 3-colorings, Michigan Math. J. 10 (1963) 303-310. Zbl0115.40903
  11. [11] N. Robertson, D. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory (B) 70 (1997) 145-161, doi: 10.1006/jctb.1997.1750. Zbl0883.05056
  12. [12] V. Rödl, A generalization of Ramsey theorem (Ph.D. thesis, Charles University, Prague, Czech Republic, 1973) 211-220. 
  13. [13] R. Steinberg and C.A. Tovey, Planar Ramsey number, J. Combin. Theory (B) 59 (1993) 288-296, doi: 10.1006/jctb.1993.1070. Zbl0794.05091
  14. [14] K. Walker, The analog of Ramsey numbers for planar graphs, Bull. London Math. Soc. 1 (1969) 187-190, doi: 10.1112/blms/1.2.187. Zbl0184.27705

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.