An invariant for minimum triangle-free graphs

Oliver Krüger

paper

An invariant for minimum triangle-free graphs

arXiv:1608.07489

Abstract

We study the number of edges, $e (G)$ , in triangle-free graphs with a prescribed number of vertices, $n (G)$ , independence number, $α (G)$ , and number of cycles of length four, $N (C_{4}; G)$ . We in particular show that $3 e (G) - 17 n (G) + 35 α (G) + N (C_{4}; G) \geq 0$ for all triangle-free graphs $G$ . We also characterise the graphs that satisfy this inequality with equality.