Abstract
For fixed integersp, q an edge coloring of a complete graphK is called a (p, q)-coloring if the edges of everyK p ⊑K are colored with at leastq distinct colors. Clearly, (p, 2)-colorings are the classical Ramsey colorings without monochromaticK p subgraphs. Letf(n, p, q) be the minimum number of colors needed for a (p, q)-coloring ofK n . 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
W. G. Brown, P. Erdős, V. T. Sós: Some extremal problems onr-graphs, inNew directions in the theory of Graphs, Proc. 3rd Ann Arbor Conference on Graph Theory, 53–63, Academic Press, New York, 1973.
W. G. Brown, P. Erdős, V. T. Sós: On the existence of triangulated spheres in 3-graphs and related problems,Periodica Mathematica Hungarica,3 (1973), 221–228.
P. Erdős: Solved and unsolved problems in combinatorics and combinatorial number theory,Congressus Numerantium,32 (1981), 49–62.
P. Erdős: Extremal problems in graph theory, inTheory of Graphs and its Applications (M. Fiedler, ed.), Academic Press, New York, 1964, 29–36.
P. Erdős, D. J. Kleitman: On coloring graphs to maximize the proportion of multicoloredk-edges,J. of Combinatorial Theory,5 (1968), 164–169.
P. Erdős, L. Lovász: Problems and results on 3-chromatic hypergraphs and some related problems, in:Infinite and Finite sets, Colloquia Math. Soc. J. Bolyai vol. 10 (A. Hajnal et al eds.) North-Holland, Amsterdam, 609–617 1995.
P. Erdős, V. T. Sós: personal communication, 1994.
P. C. Fishburn: personal communication, 1995.
A. Gyárfás, J. Lehel: Linear Sets with Five Distinct Differences among any Four Elements,J. of Combinatorial Theory B,64 (1995), 108–118.
I. Z. Ruzsa, E. Szemerédi: Triple systems with no six points carrying three triangles, inCombinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai 18, Volume II. 939–945.
W. D. Wallis: Combinatorial Designs, Monographs and Textbooks inPure and Applied Mathematics, Vol. 118, Marcel Dekker, Inc. 1988.
Author information
Authors and Affiliations
Additional information
Supported by OTKA grant 16414.
Rights and permissions
About this article
Cite this article
Erdős, P., Gyárfás, A. A variant of the classical Ramsey problem. Combinatorica 17, 459–467 (1997). https://doi.org/10.1007/BF01195000
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01195000