The maximum number of triangles in a K4-free graph

✍ Scribed by Jürgen Eckhoff

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 448 KB
• Volume: 194
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00120-4

✦ Synopsis

Let v, e and t denote the number of vertices, edges and triangles, respectively, of a K4-free graph. Fisher (1988) proved that t<,(e/3) 3/2, independently of v. His bound is attained when e = 3k 2 for some integer k, but not in general. We find here, for any given value of e, the maximum possible value of t. Again, the maximum does not depend on v. We also show that certain 'gaps' occur in the set of triples (v, e, t) realizable by K4-free graphs. (~