# 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.