Name
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 [n(2)/4] + 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, Erdos, and Lovasz-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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1002/jgt.22768 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
color critical graphs, Erdos-Rademacher problem, triangle covering number | Journal | 100 |
Issue | ISSN | Citations |
1 | 0364-9024 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xizhi Liu | 1 | 0 | 1.35 |
| Dhruv Mubayi | 2 | 0 | 0.68 |