The minimum number of 4-cliques in graphs with triangle-free complement

2005/01/14 by Vladimir Nikiforov, Nikiforov, Vladimir
Computer Science · Engineering · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C35

paper · pdf · doi:10.48550/arxiv.math/0501211

8 pages

arxiv created 2005/01/14 · openalex publication_date 2005/01/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Write f(n) for the minimum number of 4-cliques in graphs of order n with triangle-free complement. Finding f(n) is a particular case of a problem raised by Erdos in 1962. We give an upper bound of f(n) and a matching lower bound when the graph is close to regular.

Related

• A problem of Erdős on the minimum number of k-cliques
• Minimum Number of k-Cliques in Graphs with Bounded Independence Number
• The number of cliques in graphs of given order and size
• On the number of triangles in K₄-free graphs
• On the Ramsey-Turán problem for 4-cliques