\(2\)-coloring \(K_4\)-free graphs to avoid monochromatic triangles

A problem on triangle-free subgraphs in graphs containing no \(K_4\) (proposed by Erdös[1]), ($100)

Let \(f(p, k_1, k_2)\) denote the smallest integer \(n\) such that there is a graph \(G\) with \(n\) vertices satisfying the properties:
  • 1. Any edge coloring in \(p\) colors contains a monochromatic \(K_{k_1}\)
  • 2. \(G\) contains no \(K_{k_2}\)
Prove or disprove: \[ f(2,3,4) < 10^{6}. \]

Erdös and Hajnal [1][2] conjectured that for any \( k\) there exists a graph \( G_k\) which contains no \( K_{k+1}\) but if one colors the edges of \( G_k\) by two (or in general \( p\)) colors in any arbitrary way, there is always a monochromatic \( K_k\). This conjecture was proved by Folkman [3] for \( p=2\). The general conjecture was proved by Nešetril and Rödl[8]. However, both Folkman's and Nešetril and Rödl's upper bounds for \( f(2,3,4)\) are extremely large (greater than a ten-times iterated exponential).

On the other hand, Graham [5] showed that \( f(2,3,6)=8\) (by using \( K_8 \setminus C_5\)) and Irving [6] proved \( f(2,3,5) \leq 18\). This was further improved in [7] to \( f(2,3,5) \leq 16\).

Frankl and Rödl [4] proved that

\(\displaystyle f(2,3,4) \leq 7 \times 10^{11}. \)

Moreover, they showed that their graph has the property that any subgraph with half the total number of edges has a triangle.

Spencer[9][10] improved this slightly to \( f(2,3,4) < 3 \times 10^9\), thereby claiming a reward from Erdös for beating his challenge target of \( 10^{10}\). (The astute reader may wonder how to resolve the apparent inconsistency between the title in [9] and the given bound of \( 3 \times 10^9\). This is explained in [10].) Chung and Graham have stated they believe that \( f(2,3,4) < 1000\) may actually hold.

Bibliography
1 P. Erdösand A. Hajnal. Research Problem 2.5. J. Comb. Theory 2 (1967), 105.

2 P. Erdös, Problems and results on finite and infinite graphs, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), 183-192 (loose errata), Academia, Prague, 1975.

3 J. Folkman, Graphs with monochromatic complete subgraphs in every edge colouring, SIAM J. Appl. Math. 18 (1970), 19-29.

4 P. Frankl and V. Rödl. Large triangle-free subgraphs in graphs with \( K_4\). Graphs and Comb. 2 (1986), 135-144.

5 R. L. Graham. On edgewise \( 2\)-colored graphs with monochromatic triangles and containing no complete hexagon. J. Comb. Theory 4 (1968), 300.

6 R. W. Irving. On a bound of Graham and Spencer for a graph coloring constant. J. Comb. Theory (B) 15 (1973), 200-203.

7 N. G. Khadzhiivanov and N. D. Nenov. An example of a \( 16\)-vertex Ramsey \( (3,3)\)-graph with clique number \( 4\), (Russian). Serdica 9 (1983), 74-78.

8 J. Nešetril and V. Rödl. The Ramsey property for graphs with forbidden complete subgraphs. J. Comb. Theory (B) 20 (1976), 243-249.

9 J. H. Spencer, Three hundred million points suffice. J. Comb. Theory (A) 49 (1988), 210-217.

10 J. H. Spencer, Erratum to "Three hundred million points suffice" . J. Comb. Theory (A) 50 (1989), 323.