BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-75-488
       ENTRY:: August 23, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On complete subgraphs of r-chromatic graphs.
        TYPE:: Technical Report
      AUTHOR:: Bollabas, Bela
      AUTHOR:: Erdoes, Paul
      AUTHOR:: Szemeredi, Endre
        DATE:: April 1975
       PAGES:: 17
    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.
       NOTES:: [Adminitrivia V1/Prg/19950823]
         END:: STAN//CS-TR-75-488