A variant of the classical Ramsey problem |
| |
Authors: | Paul Erdős András Gyárfás |
| |
Affiliation: | (1) Computer and Automation Institute, Hungarian Academy of Sciences, Budapest, Hungary |
| |
Abstract: | For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyKp K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticKp subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofKn. We use the Local Lemma to give a general upper bound forf. We determine for everyp the smallestq for whichf(n, p, q) is linear inn and the smallestq for whichf(n, p, q) is quadratic inn. We show that certain special cases of the problem closely relate to Turán type hypergraph problems introduced by Brown, Erd s and T. Sós. Other cases lead to problems concerning proper edge colorings of complete graphs.Supported by OTKA grant 16414. |
| |
Keywords: | 05D10 |
本文献已被 SpringerLink 等数据库收录! |
|