On the structure of dense graphs with fixed clique number

Abstract

We study structural properties of graphs with fixed clique number and high minimum degree. In particular, we show that there exists a function $L=L(r,\epsilon )$, such that every $K_r$-free graph $G$ on $n$ vertices with minimum degree at least $(\frac{2r-5}{2r-3}+\epsilon )n$ is homomorphic to a $K_r$-free graph on at most $L$ vertices. It is known that the required minimum degree condition is approximately best possible for this result. For $r=3$ this result was obtained by Łuczak [On the structure of triangle-free graphs of large minimum degree, Combinatorica 26 (2006), no. 4, 489-493] and, more recently, Goddard and Lyle [Dense graphs with small clique number, J. Graph Theory 66 (2011), no. 4, 319-331] deduced the general case from Łuczak's result. Łuczak's proof was based on an application of Szemerédi's regularity lemma and, as a consequence, it only gave rise to a tower-type bound on $L(3,\epsilon )$. The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for $L(r,\epsilon )$ that is doubly exponential in poly($\epsilon$).

References in corpus (1)

• Coloring dense graphs via VC-dimension

Cited by in corpus (1)

• The homomorphism threshold of $\{C_3,C_5\}$-free graphs