On the number of edges not covered by monochromatic copies of a fixed graph

AbstractFor a fixed graph H, let f(n,H) denote the maximum possible number of edges not belonging to a monochromatic copy of H in a 2-edge-coloring of the complete graph of order n. Let ex(n,H) be the Turán number of H, i.e., the maximum number of edges that a graph on n vertices can have without containing a copy of H. An easy lower bound of f(n,H)⩾ex(n,H) follows from the 2-edge-coloring in which the edges of one color form the largest H-free graph. In this paper we consider the cases when H is an edge-color-critical graph (e.g., a complete graph) or a 4-cycle. We will show then, that for sufficiently large n, the value of f(n,H) is actually equal to ex(n,H)