Minimum triangle-free graphs
Stanisław Radziszowski, Donald L. Kreher · RIT Scholar Works (Rochester Institute of Technology) · 1991
We prove that e(3, k + 1, n) >= 6n - 13k where e(3, k + 1, n) is the minimum number of edges in any triangle-free graph on n vertices with no independent set of size k + 1. to achieve this we first characterize all such graphs with exactly e(3, k + 1, n) edges for n <= 3k. These results yield some sharp lower bounds for the independence ratio for trianagle-free graphs. In particular, the exact value of the minimal independence ratio for graphs with average degree 4 is shown in be 4/13. A slight improvement to the general upper bound for the classical Ramsey R(3,k) numbers is also obtained.