Turán Number of Nonbipartite Graphs and the Product Conjecture

摘要

The decomposition family of a family of graphs often helps us to determine the error term in the well-known Erdos-Stone-Simonovits theorem. We study the Turan number of families of nonbipartite graphs such that their decomposition families contain a matching and a star. To be precisely, we prove tight bounds on the Turan number of such families of graphs. Moreover, we find a graph which is a counterexample to an old conjecture of Erdos and Simonovits, while all previous counterexamples are families of graphs.

关键词