2020/05/14 by Liu, Xizhi, Mubayi, Dhruv
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2005.07224
The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers s,t and an n-vertex graph G with \lfloor n2/4 \rfloor +t edges and triangle covering number s, we determine (for large n) sharp bounds on the minimum number of triangles in G and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, Erd\H os, and Lovász-Simonovits whose results apply only to s ≤ t. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.