Turán Number of Nonbipartite Graphs and the Product Conjecture

Abstract

The decomposition family of a family of graphs often helps us to determine the error term in the well-known Erdős–Stone–Simonovits theorem. We study the Turán 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 Turán number of such families of graphs. Moreover, we find a graph which is a counterexample to an old conjecture of Erdős and Simonovits, while all previous counterexamples are families of graphs.

Keywords

Turán number / Decomposition family / Matching / Star / Product conjecture

Funding

National Natural Science Foundation of China(11601380)

Anhui Provincial Natural Science Foundation(2208085J22)

Science and Technology Commission of Shanghai Municipality(22DZ2229014)