Topics in extremal graph theory

New results are proved on several problems in extremal graph theory.Let $ex\sp*(D;H)$ denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to the graph H. It is shown that this is finite if and only if H is a disjoint union of paths. Several specific forbidden subgraphs H have been studied, and the following results have been proved:(1) $ ex\sp*(D;P\sb4) = D\sp2$ for all D, uniquely achieved by $K\sb{D,D}.$ If, in addition, the maximum clique size is $\omega$, then the number of edges is at most $D\sp2 - {D(\omega-2)\over 2}.$(2) $ex\sp*(D;P\sb5) = {2\over 27}D\sp3 + O(D\sp2).$(3) $ex\sp*(D;2P\sb3) = {1\over 8}D\sp4 +{1\over 8}D\sp3 + O(D\sp2).$(4) $ex\sp*(D;P\sb3 + P\sb2)< 2D\sp2.$ If $K\sb3$ is also forbidden, then $ex\sp*(D;P\sb3 + P\sb2, K\sb3) = {5\over 4}D\sp2 + O(D).$The p-intersection number of a graph G, denoted by $\theta\sb{p}(G),$ is the minimum size of a set $\cup\sb{v\in V(G)}S\sb{v}$ such that u and v are adjacent if and only if $\vert S\sb{u}\cup S\sb{v}\vert \ge p.$ It is proved here that $\theta\sb{p}(K\sb{n,n})\ge (n\sp2 + (2p - 1)n)/p$ for $p\ge 2.$ Furthermore, $\theta\sb2(K\sb{n,n}) = (n\sp2 + 3n)/2$ is achieved using a graph design called orthogonal double covering. For sufficiently large p, the residual intersection number, denoted by $\theta\sp*(G),$ is defined and studied here as the limiting value of $f\sb{p}(G) = \theta\sb{p}(G)-p.$ The maximum values of n such that $\theta\sp*(K\sb{2,n}) = 5,6$ and 7 are 4, 7, and 14, respectively. Asymptotically, $\theta\sp*(K\sb{2,n}) = \log\sb2 n + o(\log\sb2 n).$An $(n,m,r)$-rainbow-free coloring is a multi-edge-coloring of edges in $K\sb{n}$ with at most m colors such that the edges of each color form a clique and it is not possible to choose distinct colors for each edge in any r-cycle. The maximum value of the sum of the numbers of colors appearing on each edge over all $(n,m,r)$-rainbow-free colorings, denoted by $e(n,m,r),$ was originally investigated by S. Roman. The bounds he demonstrated have been improved upon in this thesis. It is shown that $e(n,m,3) = 2{n-1\choose 2} + m - 1,$ and that $e(n,m,4)\le 3{n\choose 2} + m.$U of I OnlyETDs are only available to UIUC Users without author permissio