Extremal graphs for edge blow-up of graphs.

Given a graph H and an integer p , the edge blow-up H p + 1 of H is the graph obtained from replacing each edge in H by a clique of order p + 1 where the new vertices of the cliques are all distinct. The Turán numbers for edge blow-up of matchings were first studied by Erdős and Moon. In this paper, we determine the range of the Turán numbers for edge blow-up of all bipartite graphs and the exact Turán numbers for edge blow-up of all non-bipartite graphs. In addition, we characterize the extremal graphs for edge blow-up of all non-bipartite graphs. Our results also extend several known results, including the Turán numbers for edge blow-up of stars, paths and cycles. The method we used can also be applied to find a family of counter-examples to a conjecture posed by Keevash and Sudakov in 2004 concerning the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of K n. [ABSTRACT FROM AUTHOR]