Erdős, Pál and Simonovits, Miklós and T. Sós, Vera (1975) AntiRamsey theorems. In: Infinite and finite sets : To Paul Erdős on his 60th birthday. NorthHolland Publishing Company, Amsterdam, pp. 633643. ISBN 0720428149

Text
197505.pdf Download (1MB)  Preview 
Abstract
Let c be an edgecolouring of the complete ngraph Kn with m colours. A totally multicoloured (TMC) subgraph of Kn (with respect to c) is a graph G⊆Kn such that no two edges of G have the same colour. Let H be a graph with less than n vertices. If m is sufficiently large then there is in Kn a TMC subgraph isomorphic to H. Let f(n,H) denote the maximal number m such that there is an mcolouring of Kn without a TMCsubgraph isomorphic to H. Put d=min(χ(H−e),e∈E(H))−1. It is shown that f(n,H)/(n2) converges to 1−1/d for n→∞. An analogous result is proved for uniform hypergraphs. If, especially, H is a complete graph Kp, the extremal colouring is, for every n, uniquely determined (up to isomorphisms); it is closely related to the Turán graph (with p−1 colourclasses). The problem of determining f(n,H) is also discussed in more detail in the case when H is a path or a circuit, and in the case of a path an explicit formula is given, holding for n sufficiently large.
Item Type:  Book Section 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  25 Jun 2020 17:05 
Last Modified:  25 Jun 2020 17:05 
URI:  http://real.mtak.hu/id/eprint/110457 
Actions (login required)
Edit Item 