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: Ramseyan Properties of Graphs by Ermelinda DeLaVina. | Ramseyan Properties of Graphs by Ermelinda DeLaVina delavina@ Siemion Fajtlowicz siemion@ University of Houston Houston Texas 77024 Submitted February 19 1996 Accepted August 28 1996 Abstract. Every graph of chromatic number k with more than k r 1 b 1 vertices has a b-element independent set of vertices such that if any two of them are joined by an edge then the chromatic number stays the same or a r-element independent set of vertices such that joining any two of them by an edge increases the chromatic number. 0. Introduction. Let P be a class of graphs and let X and y be a pair of non-adjacent distinct vertices of G P. For every graph consider a hxed coloring of all pairs X yg of nonadjacent vertices - we color e X yg blue if G eg belongs to P and red - otherwise. A class . a property P of graphs will be called Ramseyan if large graphs from P contain large monochromatic subgraphs. It is easy to see that P is Ramseyan if and only if large enough graphs from P have large independent sets. The necessity of this condition is obvious and the sufficiency follows from Ramsey THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R26 2 theorem applied to the red-blue coloring of 2-element subsets of a large independent set. Given a Ramseyan class of graphs P we put P r b to be the smallest integer n such every graph from P with n or more elements contains a r-element red clique or a b-element blue clique. Graphs of maximum order without this property will be called P r b critical. The goal of this paper is to prove the following Theorem. If P is the class of all graphs of chromatic number k then P r b 1 k r 1 b 1 . Our theorem was conjectured by the hrst author who also proved it in some cases and established all lower bounds. Examples of critical P r b graphs are disjoint unions of b 1 copies of of complete k-partite graphs in which every part has r 1 vertices. Other critical graphs can be obtained by adding extra edges to these examples but the .
