论文标题
关于广义的erdős-rademacher问题
On a generalized Erdős-Rademacher problem
论文作者
论文摘要
覆盖图的三角形是击中所有三角形的顶点的最小数量。给定正整数$ s，t $和$ n $ vertex Graph $ g $，带有$ \ lfloor n^2/4 \ rfloor +t $ +t $ edge and triangle覆盖数字$ s $，我们确定（对于大$ n $）（对于$ n $）上的最低三角形数量$ g $，还描述了极端构造。对于较大尺寸和颜色关键图的集团，也证明了类似的结果。 这扩展了Rademacher，Erd \ H OS和Lovász-Simonovits的经典作品，其结果仅适用于$ s \ le t $。我们的结果还涉及Xiao和Katona的两个猜想。我们证明了其中一个并给出反例，并证明了其他猜想的修改版本。
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.
