Fundamental Groups of Neighborhood Complexes
Vol. 24 (2017), No. 3, Page 321-353.
Matsushita, Takahiro
Fundamental Groups of Neighborhood Complexes
[Full Article (PDF)] [MathSciNet Review (HTML)] [MathSciNet Review (PDF)]
Abstract:
The neighborhood complexes of graphs were introduced by Lovász 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(KG_{2k+1,k})$ is isomorphic to $\mathbb{Z} / 2$, and this implies that there is no graph homomorphism from $KG_{2k+1,k}$ to the 5-cycle graph $C_5$. We discuss the covering maps associated to $r$-fundamental groups.
Keywords: Graphs, graph homomorphisms, neighborhood complexes, fundamental groups
Mathematics Subject Classification (2010): 55Q05
Mathematical Reviews Number: MR3700486
Received: 2016-02-12
