Edges Not Covered by Monochromatic Bipartite Graph

Let f_k(n,H) denote the maximum number of edges not contained in any monochromatic copy of H in a k-coloring of the edges of Kn, and let ex(n,H) denote the Tur\'an number of H. In place of f2(n,H) we simply write f(n,H). Keevash and Sudakov proved that f(n,H) = ex(n,H) if H is an edge-critical graph or C4 and asked if this equality holds for any graph H. All known exact values of this question require H to contain at least one cycle. In this paper we focus on acyclic graphs and present the following results: (1) We prove f(n,H) = ex(n,H) when H is a spider or a double broom. (2) We show that a tail in H is a path P3 = v0v1v2 such that v2 is only adjacent to v1, and v1 is only adjacent to v0,v2 in H. We obtain a tight upper bound for f(n,H) when H is a bipartite graph with a tail. This result provides the first bipartite graphs which answer the question of Keevash and Sudakov in the negative. (3) We answer a question of Liu, Pikhurko, and Sharifzadeh who asked if f_k(n,T) = (k-1)ex(n,T) when T is a tree. We provide an upper bound for f_2k(n,P_2k) and show it is tight when 2k- 1 is prime. This provides a negative answer to their question.