Counting substructures. I: Color critical graphs (Q1959675)

Colour critical graphs are graphs containing an edge whose deletion reduces the chromatic number of the graph. A critical graph \(G\) is called \(r\)-critical if it has chromatic number \(r+ 1\). Let \(G\) be an \(r\)-critical graph with \(r\geq 2\). Then \(c(n, G)\) denotes the minimum number of copies of \(G\) in the graph obtained from the Turán graph \(T_r(n)\) by adding one edge. Let \(t_r(n)\) denote the number of edges of \(T_r(n)\). The author obtains the result that there exists a \(\delta> 0\) such that if \(n\) is sufficiently large and \(1\leq q< \delta n\), then every graph with \(n\) vertices and \(t_r(n)+ q\) edges contains at least \(qc(n, G)\) copies of \(G\). This result is asymptotically sharp.