When is an almost monochromatic K4 guaranteed?

Alexandr Kostochka, Dhruv Mubayi

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)823-830
Number of pages8
JournalCombinatorics Probability and Computing
Issue number6
StatePublished - Nov 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'When is an almost monochromatic K4 guaranteed?'. Together they form a unique fingerprint.

Cite this