Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs (Q1740361)

\textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] defined the neighborhood complex $\mathcal{N}(G)$ of a graph $G$ to be the simplicial complex whose vertices are the non-isolated vertices of $G$ and whose simplices are the subsets of $V(G)$ having a common neighbor. Lovász [loc. cit.] proved that if $\mathcal{N}(G)$ is $k$-connected (in the sense of topological connectivity), then $\chi(G) \geq k+3$. \par This paper computes the homotopy type of $\mathcal{N}(G)$ when $G$ is either a graph of maximum degree at most $3$, or a $4$-regular circulant graph $C_n(s,t)$, where $C_n(s,t)$ is the graph on vertex set $\{1, \ldots, n\}$ where $xy \in E(G)$ if and only if $|x-y| \in \{s,t\}$.