tailieunhanh - Báo cáo toán học: "On some Ramsey and Tur´n-type numbers for paths a and cycles"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: On some Ramsey and Tur´n-type numbers for paths a and cycles. | On some Ramsey and Turan-type numbers for paths and cycles Tomasz Dzido Institute of Mathematics University of Gdansk Wita Stwosza 57 80-952 Gdansk Poland tdz@ Marek Kubale Algorithms and System Modelling Department Gdansk University of Technology G. Narutowicza 11 12 80-952 Gdansk Poland kubale@ Konrad Piwakowski Algorithms and System Modelling Department Gdansk University of Technology G. Narutowicza 11 12 80-952 Gdansk Poland coni@ Submitted Nov 15 2005 Accepted Jul 3 2006 Published Jul 11 2006 Mathematics Subject Classifications 05C55 05C15 05C38 Abstract For given graphs G1 G2 . Gk where k 2 the multicolor Ramsey number R G1 G2 . Gk is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors there is always a monochromatic copy of Gi colored with i for some 1 i k. Let Pk resp. Ck be the path resp. cycle on k vertices. In the paper we show that R P3 Ck Ck R Ck Ck 2k 1 for odd k. In addition we provide the exact values for Ramsey numbers R P4 P4 Ck k 2 and R P3 P5 Ck k 1. 1 Introduction In this paper all graphs considered are undirected finite and contain neither loops nor multiple edges. Let G be such a graph. The vertex set of G is denoted by V G the edge set of G by E G and the number of edges in G by e G . Cm denotes the cycle of length m and Pm - the path on m vertices. For given graphs Gi G2 . Gk k 2 the multicolor Ramsey number R G-1 G2 . Gk is the smallest integer n such that if we arbitrarily color the edges of the complete graph of order n with k colors then it always contains a monochromatic copy of Gi colored with i for some 1 i k. We only THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R55 1 consider 3-color Ramsey numbers R G1 G2 G3 in other words we color the edges of Kn with colors red blue and green . The Turan number T n G is the maximum number of edges in any n-vertex graph which does not contain a subgraph isomorphic to G. By T n G we denote