Report Number: CS-TR-75-488
Institution: Stanford University, Department of Computer Science
Title: On complete subgraphs of r-chromatic graphs.
Author: Bollabas, Bela
Author: Erdoes, Paul
Author: Szemeredi, Endre
Date: April 1975
Abstract: Denote by G(p,q) a graph of p vertices and q edges. $K_r$ = G(r,($(^{r}_{2}$)) is the complete graph with r vertices and $K_r$(t) is the complete r chromatic (i.e., r-partite) graph with t vertices in each color class. $G_r$(n) denotes an r-chromatic graph, and $\delta$(G) is the minimal degree of a vertex of graph G. Furthermore denote by $f_r$(n) the smalleest integer so that every $G_r$(n) with $\delta${$G_r$(n)) > $f_r$(n) contains a $K_r$. It is easy to see that $\lim_{n \rightarrow \infty} f_r$(n)/n = $c_r$ exists. We show that $c_4 \geq$ 2 + 1/9 and $c_r \geq$ r-2 + 1/2 - $\frac{1}{2(r-2)}$ for r > 4. We prove that if $\delta${$G_3$(n)) $\geq$ n+t then G contains at least $t^3$ triangles but does not have to contain more than 4$t^3$ of them.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/488/CS-TR-75-488.pdf