Higher independence complexes of graphs and their homotopy types

zbMATH Open1469.05168arXiv2001.05448MaRDI QIDQ5003757FDOQ5003757

Authors: Priyavrat Deshpande, Anurag Singh 

Publication date: 29 July 2021

Abstract: For $rgeq1$, the $r$-independence complex of a graph $G$ is a simplicial complex whose faces are subset $IsubseteqV(G)$ such that each component of the induced subgraph $G[I]$ has at most $r$ vertices. In this article, we determine the homotopy type of $r$-independence complexes of certain families of graphs including complete $s$-partite graphs, fully whiskered graphs, cycle graphs and perfect $m$-ary trees. In each case, these complexes are either homotopic to a wedge of equi-dimensional spheres or are contractible. We also give a closed form formula for their homotopy types.

Full work available at URL: https://arxiv.org/abs/2001.05448

Recommendations

• scientific article; zbMATH DE number 7499158
• Independence complexes of chordal graphs
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Chordal graphs, higher independence and vertex decomposable complexes
• scientific article; zbMATH DE number 1559018

zbMATH Keywords

simplicial complexhomotopy type\(r\)-independence complexes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of simplicial complexes (05E45) Classification of homotopy type (55P15) Relations of low-dimensional topology with graph theory (57M15)

Cites Work

• Morse theory for cell complexes
• Simplicial complexes of graphs
• Combinatorial algebraic topology
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Complexes of directed trees
• Proof of the Lovász conjecture
• Vertex decomposable graphs and obstructions to shellability
• Star clusters in independence complexes of graphs
• The topology of the independence complex
• On the independence complex of square grids
• Certain homology cycles of the independence complex of grids
• Domination numbers and homology
• Title not available (Why is that?)
• Independence complexes of chordal graphs
• The homology of ``\(k\)-equal manifolds and related partition lattices
• Distance domination and distance irredundance in graphs
• A note on distance domination numbers of graphs
• On the \(r\)-domination number of a graph
• Generalizations of independence and chromatic numbers of a graph
• Bounded monochromatic components for random graphs
• Homotopy type of neighborhood complexes of Kneser graphs, \(KG_{2,k}\)
• Defective and clustered graph colouring
• Weighted sheaves and homology of Artin groups
• Matching and independence complexes related to small grids

Cited In (26)

• Topology of cut complexes of graphs
• Title not available (Why is that?)
• Splittings of independence complexes and the powers of cycles
• Homotopy type of the neighborhood complexes of graphs of maximal degree at most 3 and 4-regular circulant graphs
• Title not available (Why is that?)
• Homotopy types of the Hom complexes of graphs
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Independence complexes of chordal graphs
• Homotopy type of circle graph complexes motivated by extreme Khovanov homology
• Independence complexes of comaximal graphs of commutative rings with identity
• On the Simple ℤ₂-homotopy Types of Graph Complexes and Their Simple ℤ₂-universality
• The homotopy type of the independence complex of graphs with no induced cycles of length divisible by 3
• On the homotopy types of the independence complexes of grid graphs with cylindrical identification
• On the homology of independence complexes
• Title not available (Why is that?)
• Homotopy type of the independence complex of some categorical products of graphs
• Independence complexes and edge covering complexes via Alexander duality
• Chordal graphs, higher independence and vertex decomposable complexes
• Star clusters in independence complexes of graphs
• Dominance complexes and vertex cover numbers of graphs
• Title not available (Why is that?)
• Higher hairy graph homology
• Independence complexes and incidence graphs
• Perfect matching complexes of honeycomb graphs
• Matching trees for simplicial complexes and homotopy type of devoid complexes of graphs
• Topology of complexes of edge covering partite graphs and hypergraphs

Uses Software

• SageMath

This page was built for publication: Higher independence complexes of graphs and their homotopy types

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5003757)