A note on independence complexes of chordal graphs and dismantling

zbMATH Open1366.05123arXiv1508.02426MaRDI QIDQ2363095FDOQ2363095

Authors: Michał Adamaszek 

Publication date: 13 July 2017

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that the independence complex of a chordal graph is contractible if and only if this complex is dismantlable (strong collapsible) and it is homotopy equivalent to a sphere if and only if its core is a cross-polytopal sphere. The proof uses the properties of tree models of chordal graphs.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Independence complexes of chordal graphs
• Chordal graphs, higher independence and vertex decomposable complexes
• Homotopy types of box complexes of chordal graphs
• Foldings in graphs and relations with simplicial complexes and posets
• Complexity of simplicial homology and independence complexes of chordal graphs

zbMATH Keywords

chordal graphdismantlingindependence complexcop-win graphstrong collapsibility

Mathematics Subject Classification ID

Simplicial sets and complexes in algebraic topology (55U10) Structural characterization of families of graphs (05C75) Combinatorial aspects of simplicial complexes (05E45)

Cites Work

• Title not available (Why is that?)
• Vertex-to-vertex pursuit in a graph
• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Complexes of directed trees and independence complexes
• Algebraic properties of edge ideals via combinatorial topology
• Vertex decomposable graphs and obstructions to shellability
• Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity
• Title not available (Why is that?)
• Strong homotopy types, nerves and collapses
• Combinatorial algebraic topology
• Projective dimension, graph domination parameters, and independence complex homology
• The topology of the independence complex
• Simplicial simple-homotopy of flag complexes in terms of graphs
• Certain homology cycles of the independence complex of grids
• Splittings of independence complexes and the powers of cycles
• Cores of simplicial complexes
• Independence complexes of chordal graphs
• Linear colorings of simplicial complexes and collapsing
• Nerves of simplicial complexes
• Recognition of collapsible complexes is NP-complete
• Complexity of simplicial homology and independence complexes of chordal graphs

Cited In (7)

• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Independence complexes of chordal graphs
• On the homology of independence complexes
• Minimal graphs for contractible and dismantlable properties
• A hierarchy of dismantlings in graphs
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs
• \(R\)-annihilated and independent perfect neighborhood sets in chordal graphs

This page was built for publication: A note on independence complexes of chordal graphs and dismantling

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