Dissertation Title:          Graph-Theoretic Simplicial Complexes, Haj\’os-Type Constructions, and $k$-Matchings

Abstract Title:  A graph property is monotone if it is closed under the removal of edges and vertices. Given a graph $G$ and a monotone graph property $P$, one can associate to the pair $(G,P)$ a simplicial complex, which serves as a way to encode graph properties within faces of a topological space. We study these graph-theoretic simplicial complexes using combinatorial and topological approaches as a way to inform our understanding of the graphs and graph properties.  In this dissertation, we study two families of simplicial complexes: (1) neighborhood complexes and (2) $k$-matching complexes. A neighborhood complex is a simplicial complex of a graph with vertex set the vertices of the graph and facets given by neighborhoods of each vertex of the graph. In 1978, Lov\’asz used neighborhood complexes as a tool for studying lower bounds for the chromatic number of graphs. In this dissertation, we will prove results about at the connectivity of neighborhood complexes in relation to Haj\’os-type constructions and analyze randomly generated graphs arising from two Haj\’os-type stochastic algorithms using SageMath.  The second part of the dissertation will focus on $k$-matching complexes. A $k$-matching complex of a graph is a simplicial complex with vertex set given by edges of the graph and faces given sets of edges in the graph such that each vertex of the induced graph has degree at most $k$. For example, the faces of a $1$-matching complex are given by subsets of disjoint edges. We build up the study of $k$-matching complexes and in particular study of the $2$-matching complexes of wheel graphs and caterpillar graphs.