In this thesis, we examine several problems from extremal graph theory. In particular, we fix a class $/cal[G]$ of graphs, and attempt to maximize and/or minimize various functions (graph invariants) from $/cal[G]$ to the nonnegative integers. When possible, we also describe the graphs that attain these extrema.
We first consider the problem of finding (bounds for) f(v,e, λ), which is the maximum number of proper vertex colorings of a (v, e)-graph (a graph with v vertices and e edges) in λ colors. Although we give lower and upper bounds for f(v, e, λ), our main result is the improvement of the known upper bounds for f(v,ce, 3). To do this, we introduce a new notion of pseudo-proper colorings of a graph. Some discussion is given about the quality of the bounds obtained and possible extensions of our results.
We also consider the following variation of a Ramsey problem. Suppose that e edges of Kv are colored red and $ (/sbsp[2][v] ) - e$ of the edges are colored blue. We examine the problems of finding the maximum and minimum number of monochromatic triangles, 3-paths, and 3-stars in such a coloring. In each case, the problem is reduced to finding the maximum and minimum number of paths of length two in a (v, e)-graph. We solve this problem and also completely classify the (v, e)-graphs which attain these maximums or minimums.
Finally, we show that the number of 4-cliques appearing in a 4-partite graph G of size e is at most $[e/sp2/over36]$ We conjecture that a Ks+1-free graph contains at most $ (e/ (/sbsp[2][s] ) )/sp[s/over2]$ s-cliques, with equality if and only if a (the) nontrivial component of the graph is the Turan graph T$/sb[s](/sqrt[2se/over s-1]).$