On a generalized Erdős-Rademacher problem
Abstract
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 n^2/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 \le 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.
- Publication:
-
arXiv e-prints
- Pub Date:
- May 2020
- DOI:
- arXiv:
- arXiv:2005.07224
- Bibcode:
- 2020arXiv200507224L
- Keywords:
-
- Mathematics - Combinatorics
- E-Print:
- 21 pages, 1 figure