A note on independence complexes of chordal graphs and dismantling

MaRDI QIDQ2363095zbMATH OpenFDO

Authors Michał Adamaszek

Publication date 13 July 2017

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

Full work available at URL https://arxiv.org/abs/1508.02426, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p34

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

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)

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.

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

Cites work

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

Cited in

(7)

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