Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On some Ramsey numbers for quadrilaterals. | On some Ramsey numbers for quadrilaterals Janusz Dybizbanski Tomasz Dzido Institute of Informatics University of Gdansk Poland jdybiz@ tdz@ Submitted Mar 31 2011 Accepted Jul 18 2011 Published Jul 29 2011 Mathematics Subject Classifications 05C55 05C15 Abstract We will prove that R C4 C4 K4 e 16. This fills one of the gaps in the tables presented in a 1996 paper by Arste et al. Moreover by using computer methods we improve lower and upper bounds for some other multicolor Ramsey numbers involving quadrilateral C4. We consider 3 and 4-color numbers our results improve known bounds. 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 Pm the path on m vertices and Km e - the complete graph on m vertices without one edge. For given graphs G1 G2 . Gk k 2 the multicolor Ramsey number R Gi 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 Gt colored with i for some 1 i k. A coloring of the edges of n-vertex complete graph with m colors is called a G1 G2 . Gm n - coloring if it does not contain a subgraph isomorphic to Gi colored with i for each i. 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. A graph on n vertices is said to be extremal with respect to G if it does not contain a subgraph isomorphic to G and has exactly T n G edges. G1 u G2 denotes the graph which consists of two disconnected subgraphs G1 and G2. kG stands for the graph consisting of k disconnected subgraphs G. We will use the following Theorem 1 Woodall 4 Let G be a graph on n n 3 vertices with more than n edges. Then G contains a cycle of length k for each k 3
