Abstract
A simple graph-product type construction shows that for all natural numbers r≥q, there exists an edge-coloring of the complete graph on 2r vertices using r colors where the graph consisting of the union of any q color classes has chromatic number 2q. We show that for each fixed natural number q, if there exists an edge-coloring of the complete graph on n vertices using r colors where the graph consisting of the union of any q color classes has chromatic number at most 2q − 1, then n must be sub-exponential in r. This answers a question of Conlon, Fox, Lee, and Sudakov.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
D. Conlon, J. Fox, C. Lee and B. Sudakov: On the grid Ramsey problem and related questions, Int. Math. Res. Not..
D. Conlon, J. Fox, C. Lee and B. Sudakov: The Erdős-Gyárfás problem on generalized Ramsey numbers, Proc. London Math. Soc., to appear.
D. Eichhorn and D. Mubayi: Edge-coloring cliques with many colors on subcliques, Combinatorica 20 (2000), 441–444.
P. Erdős: Problems and results on finite and infinite graphs, in: Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 183–192, Academia, Prague, 1975.
P. Erdős: Solved and unsolved problems in combinatorics and combinatorial number theory, in: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), Congr. Numer. 32 (1981), 49–62.
P. Erdős and A. Gyárfás: A variant of the classical Ramsey problem, Combinatorica 17 (1997), 459–467.
S. Gerke, Y. Kohayakawa, V. Rödl and A. Steger: Small subsets inherit sparse ε-regularity, J. Combin. Theory Ser. B 97 (2007), 34–56.
D. Mubayi: Edge-coloring cliques with three colors on all 4-cliques, Combinatorica 18 (1998), 293–296.
Y. Peng, V. Rödl and A. Ruciński: Holes in graphs, Electron. J. Combin. 9 (2002), Research Papers 1.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported by NSF Grant DMS-1362326.
Rights and permissions
About this article
Cite this article
Lee, C., Tran, B. The Sub-Exponential Transition for the Chromatic Generalized Ramsey Numbers. Combinatorica 39, 355–376 (2019). https://doi.org/10.1007/s00493-017-3474-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-017-3474-6