Counting Cliques Without Generalized Theta Graphs

ABSTRACT The generalized Turán number is the maximum possible number of copies of in an ‐free graph on vertices for any two graphs and . For the book graph , there is a close connection between and the Ruzsa‐Szemerédi triangle removal lemma. Motivated by this, in this paper, we study the generalized Turán problem for generalized theta graphs, a natural extension of book graphs. Our main result provides a complete characterization of the magnitude of when is a generalized theta graph, indicating when it is quadratic, when it is nearly quadratic, and when it is subquadratic. Furthermore, as an application, we obtain the exact value of , where is an edge‐critical generalized theta graph, and , extending several recent results.