Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T10:49:42.238Z Has data issue: false hasContentIssue false
  • English
  • Français

When is an Almost Monochromatic K4 Guaranteed?

Published online by Cambridge University Press:  01 November 2008

ALEXANDR KOSTOCHKA  and
DHRUV MUBAYI
ALEXANDR KOSTOCHKA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, USA and Institute of Mathematics, Novosibirsk, Russia (e-mail: kostochk@math.uiuc.edu)
DHRUV MUBAYI
Affiliation:
Department of Mathematics, Statistics, and Computer Science, University of Illinois, 851 S. Morgan Street, Chicago, IL 60607-704, USA (e-mail: mubayi@math.uic.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Suppose that n > (log k)ck, where c is a fixed positive constant. We prove that, no matter how the edges of Kn are coloured with k colours, there is a copy of K4 whose edges receive at most two colours. This improves the previous best bound of kc′k, where c′ is a fixed positive constant, which follows from results on classical Ramsey numbers.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 6 , November 2008 , pp. 823 - 830
Copyright
Copyright © Cambridge University Press 2008

References

[1]Eichhorn, D. and Mubayi, D. (2000) Edge-coloring cliques with many colors on subcliques. Combinatorica 20 441–444.CrossRefGoogle Scholar
[2]Erdös, P. (1981) Solved and unsolved problems in combinatorics and combinatorial number theory. Congressus Numerantium 32 49–62.Google Scholar
[3]Erdös, P. and Gyárfás, A. (1997) A variant of the classical Ramsey problem. Combinatorica 17 459–467.CrossRefGoogle Scholar
[4]Kostochka, A. and Rödl, V. (2001) On graphs with small Ramsey numbers. J. Graph Theory 37 198–204.CrossRefGoogle Scholar
[5]Mubayi, D. (1998) Edge-coloring cliques with three colors on all 4-cliques. Combinatorica 18 293–296.CrossRefGoogle Scholar
[6]Mubayi, D. (2004) An explicit construction for a Ramsey problem. Combinatorica 24 313–324.CrossRefGoogle Scholar
[7]Sárközy, G. and Selkow, S. (2001) On edge colorings with at least q colors in every subset of p vertices. Electron. J. Combin. 8 R9.CrossRefGoogle Scholar
[8]Sárközy, G. and Selkow, S. (2003) An application of the regularity lemma in generalized Ramsey theory. J. Graph Theory 44 39–49.CrossRefGoogle Scholar
[9]Sudakov, B. (2003) A few remarks on Ramsey–Turán-type problems. J. Combin. Theory Ser. B 88 99–106.CrossRefGoogle Scholar