Neighborhood Complexes of Kneser Graphs, KG_3,k

2018/07/31 by Nandini Nilakantan, Anurag Singh, Nilakantan, Nandini +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis #primary 05C15 #secondary 57M15

paper · pdf · doi:10.48550/arxiv.1807.11732

openalex publication_date 2018/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this article, we prove that the neighborhood complex of the Kneser graph KG_3,k is of the same homotopy type as that of a wedge of ((k+1)(k+3)(k+4)(k+6))/(4)+1 spheres of dimension k. We construct a maximal subgraph S_3,k of KG_3,k, whose neighborhood complex deformation retracts onto the neighborhood complex of SG_3,k.

Related

• Deformation Retracts of Neighborhood Complexes of Stable Kneser Graphs
• On the neighborhood complex of s-stable Kneser graphs
• Generalization of neighborhood complexes
• Neighborhood Complexes of induced k-independent graphs
• Neighborhood complexes, homotopy test graphs and a contribution to a conjecture of Hedetniemi