RAMSEY-TYPE PROBLEM FOR AN ALMOST MONOCHROMATIC K_4

摘要

In this short note we prove that there is a constant c such that every k-edge-coloring of the complete graph K_n with n ≥ 2~(ck) contains a K_4 whose edges receive at most two colors. This improves on a result of Kostochka and Mubayi, and is the first exponential bound for this problem.