For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex $\text{Hom}(G,K_m)$ is at least $m-D(G)-2$, where $D(G)=\max_{H\subseteq G}\delta(H)$, for $\delta(H)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of Cukic and Kozlov, in which the maximum degree $\Delta(G)$ was used in place of $D(G)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi(G)\leq D(G)+1$, as $\chi(G) = \min\lbrace m: \text{Hom}(G,K_m) \ne\emptyset\rbrace$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes $\text{Hom}(G(n,p),K_m)$ when $p=c/n$ for a fixed constant $c > 0$.