Geodesic
Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
Samir Shukla1
1Indian Institute of Technology Bombay
The electronic journal of combinatorics, Tome 26 (2019) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

To estimate the lower bound for the chromatic number of a graph $G$, Lovász associated a simplicial complex $\mathcal{N}(G)$ called the neighborhood complex and related the topological connectivity of $\mathcal{N}(G)$ to the chromatic number of $G$. More generally he proved that the chromatic number of $G$ is bounded below by the topological connectivity of $\mathcal{N}(G)$ plus $3$. In this article, we consider the graphs of maximal degree at most $3$ and $4$-regular circulant graphs. We show that each connected component of the neighborhood complexes of these graphs is homotopy equivalent either to a point, to a wedge sum of circles, to a wedge sum of $2$-spheres $S^2$, to $S^3$, to a garland of $2$-spheres $S^2$ or to a connected sum of tori.
DOI : 10.37236/7549
Classification : 05C15, 57M15, 05C07
Mots-clés : neighborhood complex, circulant graph

Samir Shukla  1

1 Indian Institute of Technology Bombay 
@article{10_37236_7549,
     author = {Samir Shukla},
     title = {Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {2},
     doi = {10.37236/7549},
     zbl = {1416.05116},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7549/}
}
TY  - JOUR
AU  - Samir Shukla
TI  - Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7549/
DO  - 10.37236/7549
ID  - 10_37236_7549
ER  - 
%0 Journal Article
%A Samir Shukla
%T Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/7549/
%R 10.37236/7549
%F 10_37236_7549
Samir Shukla. Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/7549

Cité par Sources :