| Understanding the structure of graphs is fundamental to advances in many areas of graph theory, as well as in many applications. In many cases, an analysis of the structure of graphs follows one of two approaches either many structural properties are considered over a restricted class of graphs, or a particular structural property is considered over many classes of graphs. Both approaches will be considered in this dissertation.Graphs which do not contain a clique of size r, i.e., Kr-free graphs, are of fundamental importance in the area of extremal graph theory. Many results have been obtained about dense triangle-free graphs, but not much is known about dense Kr-free graphs when r &ge 4. Of particular interest are results pertaining to independent sets, colorings, and homomorphisms. Another method of describing the structure of a graph is through the concept of a role assignment. A role assignment is a mapping r from a graph G to a graph GR, i.e., r : G &rarr GR, by a surjective labeling of the vertices of G with the vertices of GR, i.e., r : V(G) &rarr V( GR). For S &sube V( G), we define r(S) = { r(s) : s &isin S}. Each role assignment must satisfy the following condition: &forallv&isinVG,r Nv=N rv.The goal of this dissertation is to address the following two issues. First, what results can be obtained about the structure of dense Kr-free graphs? Secondly, what additional properties of a graph are necessary in order to obtain results about role assignments? For which classes of graphs is the problem of determining role assignments tractable, and for which classes of graphs is it difficult?In regard to the first issue, a structural theorem is obtained which allows many properties of dense Kr-free graphs to be described in terms of the properties of dense triangle-free graphs. In particular, we determine a minimum degree condition which will permit the vertices of a dense Kr-free graphs to be partitioned into sets S0, S1... Sr-3, where each set Si, 1 &le i &le r - 3, is independent, and the graph induced by the set S0 is a dense triangle-free graph. Two results regarding the size of large independent sets in Kr-free graphs are obtained, for the cases r = 4 and r &ge 5 respectively. The binding number of dense Kr-free graphs is also considered. We improve previously published results regarding the binding number by giving a construction of K4-free graphs with large binding number, and proving stricter upper bounds on the binding number of dense Kr-free graphs.In regard to the second issue, role assignments are considered for the classes of chordal graphs, strongly chordal graphs, and trees. A necessary condition is given for a chordal graph to have a role assignment to Kr for some value of r. For chordal graphs with small clique size, as well as strongly chordal graphs, this necessary condition is shown to be sufficient. Additionally, role assignments of the d-dimensional hypercube, along with graphs of similar structure, are considered. |
