| In this thesis we consider topological aspects of graph homomorphisms. Our main object of study is the Hom complex of graphs, a space first introduced by Lovasz to obtain lower bounds on chromatic number, and more recently studied by Babson and Kozlov and others in a series of papers. We prove structural results regarding the interaction of the Hom complex with several graph theoretical operations, including arbitrary products and exponentials. We introduce a notion of homotopy of graphs based on the right adjoint to the categorical product, and show that notions of graph homotopy equivalence are characterized by topological properties of the Hom complex. We relate graph homotopy to the notion of graph folding and in the process reprove a theorem of Kozlov regarding foldings preserving the homotopy type of Hom complexes.; We show that Hom complexes are 'universal' in the sense that for all connected graphs T, one can obtain an arbitrary homotopy type as Hom(T, G) for some graph G; this extends work of Csorba for T = K2. We consider notions of discrete homotopy groups and show that they can be recovered as ordinary homotopy groups of a pointed version of the Hom complex. This is related to A-theory of graphs, where one seeks a space to encode similarly defined homotopy groups based on the Cartesian product of graphs. Finally, we combine these results with work of Schultz to provide a method of constructing new 'test graphs' for bounds on chromatic number. This extends work of Schultz, who showed that the Hom complexes involving the test graphs K 2 and the odd cycles C2r +1 were related in a nice way. |
