Ramsey-type results for geometric graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Ramsey-type results for geometric graphs

Full text

Pdf (646 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 359 - 365

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Gyula Károlyi	Institute for Advanced Study, Princeton
János Pach	Hungarian Academy of Sciences
Géza Tóth	Courant Institute, NYU

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 27, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237405 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AEG94	B. Aronov, P. Erd6s, W. Goddard, D. Kleitman, M. Klugerman, J. Pach, and L. Schulman, Crossing families, Combinatorica 14 (1994), 127- 134.
	B83	J. Beck, On size Ramsey number of paths, trees, and circuits, I., Journal of Graph Theory 7 (1983), 115-129.
	BD91	A. Bialostocki and P. Dierker, On simple Hamiltonian cycles in a 2-colored complete graph, Ars Combinatoria 32 (1991), 13-16.
	BD94	A. Bialostocki and P. Dierker, Personal communication.
	B74	S.A. Burr, Generalized Ramsey theory for graphs - a survey, in: Graphs and Combznatorics (R. Bari and F. Harary, eds.), Lecture Notes in Mathematics 406, Springer-Verlag, Berlin, 1974, 52-75.
	BES75	S.A. Burr, P. Erd6s, and J.H. Spencer, Ramsey theorems for multiple copies of graphs, Transactions of the American Mathematical Society 209 (1975), 87-99.
	D50	R.P. Dilworth, A decomposition theorem for partially ordered sets, Annals of Mathematzcs 51 (1950), 161-166.
	EFR78	P. ErdSs, R.J. Faudree, C.C. Rousseau, and R.H. Schelp, The size Ramsey number, Perodica Mathcmatica Hungarica 9 (1978), 145-161.
	EG95	P. Erd6s and A. Gy~rf~s, Vertex covering with monochromatic paths, Mathematica Pannonzca 6 (1995), 7-10.
	EGP91	P. Erdős , A. Gyárfás , L. Pyber, Vertex coverings by Monochromatic cycles and trees, Journal of Combinatorial Theory Series B, v.51 n.1, p.90-95, Jan. 1991 [doi>10.1016/0095-8956(91)90007-7]
	ELS73	P. Erd6s, L. Lov~sz, A. Simmons, and E.G. Straus, Dissection graphs of planar point sets, in: A Survey of Combinatorial Theory (G. $rivastava, ed.), North-Holland, Amsterdam, 1973, 139-149.
	GG67	L. Gerencs~r and A. Gy~rf~s, On Ramseytype problems, Annales Universitatis $cientarium Budapestinensis Roland EStvSs, $ectio Mathematica X (1967), 167-170.
	GRS90	Ronald L. Graham , Bruce L. Rothschild, Ramsey theory (2nd ed.), Wiley-Interscience, New York, NY, 1990
	G83	A. Gy~rf~s, Vertex coverings by monochromatic paths and cycles, Journal of Graph Theory 7 (1983), 131-135.
	G89	A. Gy~rf~s, Covering complete graphs by monochromatic paths, in: Irregularities of Partztions (G. Haldsz and V.T. S6s, eds.), Algorithms and Combinatorics 8, Springer-Verlag, Heidelberg, 1989, 89-91.
	HKS87	A. Hajnal, P. Komj~th, L. Soukup, and I. Szalkai, Decompositions of edge colored infinite complete graphs, in: Combinatorics, Colloquza Mathematica Societatis Jdnos Bolyaz 52 (1987), 277- 280.
	JW93	K. Jansen and G. J. Woeginger, The complexity of detecting crossingfree configurations in the plane, BIT 33 (1993), no. 4, 580-595.
	KLN91	Jan Kratochvíl , Anna Lubiw , Jaroslav Nešetřil, Noncrossing subgraphs in topological layouts, SIAM Journal on Discrete Mathematics, v.4 n.2, p.223-244, May 1991 [doi>10.1137/0404022]
	KN90	J. Kratochvil and J. Neaetfil, Independent set and clique problems in intersection-defined classes of graphs, Comment. Math. Untv. Carohnae 31 (1990), 85-93.
	LMP94	D.G. Larman, J. Matouaek, J. Pach, and j. TSr6csik, A Ramsey-type result for planar convex sets, Bulletin of the London Mathematical $oczety 26 (1994), 132-136.
	PA95	J. Pach and P.K. Agarwal, Combinatorial Geometry, John Wiley, New York, 1995.
	R78	R. Rado, Monochromatic paths in graphs, in: Advances in Graph Theory (B. Bollobds, ed.), Annals of Discrete Mathematzcs 3, North-Holland, Amsterdam, 1978, 191-194.

CITED BY 2

	Gyula Károlyi , János Pach , Géza Tóth , Pavel Valtr, Ramsey-type results for geometric graphs. II, Proceedings of the thirteenth annual symposium on Computational geometry, p.94-103, June 04-06, 1997, Nice, France
	Gyula Károlyia , Vera Rosta, Generalized and geometric Ramsey numbers for cycles, Theoretical Computer Science, v.263 n.1-2, p.87-98, July 28 2001