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í toán học quốc tế đề tài: The order of monochromatic subgraphs with a given minimum degree | The order of monochromatic subgraphs with a given minimum degree Yair Caro and Raphael Yuster 1 Department of Mathematics University of Haifa at Oranim Tivon 36006 Israel Submitted Jan 10 2003 Accepted Aug 22 2003 Published Sep 8 2003 MR Subject Classifications 05C15 05C55 05C35 Abstract Let G be a graph. For a given positive integer d let fG d denote the largest integer t such that in every coloring of the edges of G with two colors there is a monochromatic subgraph with minimum degree at least d and order at least t. Let fG d 0 in case there is a 2-coloring of the edges of G with no such monochromatic subgraph. Let f n k d denote the minimum of fG d where G ranges over all graphs with n vertices and minimum degree at least k. In this paper we establish f n k d whenever k or n k are fixed and n is sufficiently large. We also consider the case where more than two colors are allowed. 1 Introduction All graphs considered in this paper are finite simple and undirected. For standard terminology used in this paper see 6 . It is well known that in any coloring of the edges of a complete graph with two colors there is a monochromatic connected spanning subgraph. This folkloristic Ramsey-type fact which is straightforward to prove has been generalized in many ways where one shows that some given properties of a graph G suffice in order to guarantee a large monochromatic subgraph of G with related given properties in any two or more than two edge-coloring of G. See . 2 3 4 5 for these types of results. In this paper we consider the property of having a certain minimum degree. e-mail yairc@ 1 e-mail raphy@ THE ELECTRONIC JOURNAL OF COMBINATORICS 10 2003 R32 1 For given positive integers d and r and a fixed graph G let fG d r denote the largest integer t such that in every coloring of the edges of the graph G with r colors there is a monochromatic subgraph with minimum degree at least d and order at least t. If G has an r-coloring of its .
