Fundamental groups of neighborhood complexes

The neighborhood complexes of graphs were introduced by Lov'asz in his proof of the Kneser conjecture. He showed that a certain topological property of $N(G)$ gives a lower bound for the chromatic number of $G$. In this paper, we study a combinatorial description of the fundamental groups of the neighborhood complexes. For a positive integer $r$, we introduce the $r$-fundamental group ${\pi }_1^r(G,v)$ of a based graph $(G,v)$ and the $r$-neighborhood complex $N_r(G)$ of $G$. The $1$-neighborhood complex is the neighborhood complex. We show that the even part ${\pi }_1^{2r}(G,v{)}_{ev}$, which is a subgroup of ${\pi }_1^{2r}(G,v)$ with index 1 or 2, is isomorphic to the fundamental group of $(N_r(G),v)$ if $v$ is not isolated. We can use the $r$-fundamental groups to show the non-existence of graph homomorphisms. For example, we show that ${\pi }_1^3(K{G}_{2k+1,k})$ is isomorphic to $\mathbb{Z}\mathrm{/}2$, and this implies that there is no graph homomorphism from $K{G}_{2k+1,k}$ to the 5-cycle graph $C_5$. We discuss the covering maps associated to $r$-fundamental groups.