ISSN:
1439-6912
Keywords:
05 C 35
;
05 C 55
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract This paper is a continuation of [10], where P. Erdős, A. Hajnal, V. T. Sós, and E. Szemerédi investigated the following problem: Assume that a so called forbidden graphL and a functionf(n)=o(n) are fixed. What is the maximum number of edges a graphG n onn vertices can have without containingL as a subgraph, and also without having more thanf(n) independent vertices? This problem is motivated by the classical Turán and Ramsey theorems, and also by some applications of the Turán theorem to geometry, analysis (in particular, potential theory) [27–29], [11–13]. In this paper we are primarily interested in the following problem. Let (G n ) be a graph sequence whereG n hasn vertices and the edges ofG n are coloured by the colours χ1,...,χ r so that the subgraph of colour χυ contains no complete subgraphK pv , (v=1,...r). Further, assume that the size of any independent set inG n iso(n) (asn→∞). What is the maximum number of edges inG n under these conditions? One of the main results of this paper is the description of a procedure yielding relatively simple sequences of asymptotically extremal graphs for the problem. In a continuation of this paper we shall investigate the problem where instead of α(G n )=o(n) we assume the stronger condition that the maximum size of aK p -free induced subgraph ofG n iso(n).
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202788
Permalink
