Edge disjoint monochromatic triangles in 2-colored graphs (Q5937583)

Let \(N(n,k)\) denote the minimum number of pairwise edge disjoint monochromatic complete graphs \(K_k\) over all 2-colorings of the edges of \(K_n\); let \(N'(n,k)\) denote the maximum of the minimum number of pairwise edge disjoint complete graphs \(K_k\) in either color 1 or color 2 in any 2-coloring of the edges of \(K_n\). The authors compute the values of \(N(n,k)\) for \(k= 3\) and \(n\leq 11\), prove several bounds and make several conjectures. Among these are: Theorem 1. \(\lim_{n\to\infty} N(n,k)/n(n- 1)\) exists and equals \(\sup_n N(n,k)/n(n- 1)\). Conjecture 1. If \(n\) is sufficiently large, \(N(n,3)= {n^2\over 12}+ o(n^2)\). Theorem 2. For \(n\geq 3\), \({3n^2\over 55}+ o(n^2)\leq N(n,3)\leq {n^2\over 12}\). Conjecture 2. If \(n\) is sufficiently large, \(N'(n,3)= {n^2\over 20}+ o(n^2)\). Theorem 3. For \(n\geq 3\), \({3n^2\over 110}+ o(n^2)\leq N(n,3)\leq {n^2\over 20}\).