tailieunhanh - Báo cáo toán học: "On some Ramsey numbers for quadrilaterals"

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

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học