\(2\)coloring \(K_4\)free graphs to avoid monochromatic triangles
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A problem on trianglefree 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}\)
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 tentimes 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
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), 183192 (loose errata), Academia,
Prague, 1975.

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

4  P. Frankl and V. Rödl. Large trianglefree subgraphs in graphs with \( K_4\). Graphs and Comb. 2 (1986), 135144.

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), 200203.

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), 7478.

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

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

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