Complexes of graphs with bounded independence number

MaRDI QIDQ5918951zbMATH OpenFDO

Authors Min-Ki Kim, Alan Lew

Publication date 14 September 2020

Published in Séminaire Lotharingien de Combinatoire (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.12605, http://www.mat.univie.ac.at/~slc/wpapers/FPSAC2020//39.html

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

\(d\)-collapsibilityhomologyrainbow independent sets

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of simplicial complexes (05E45)

Abstract: Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(fracDelta2+1ight)(n-1)ightfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.

Recommendations

• Complexes of graphs with bounded independence number
• Independence complexes and incidence graphs
• Independence complexes of well-covered circulant graphs
• On a lower bound for the connectivity of the independence complex of a graph
• scientific article; zbMATH DE number 1559018
• Independence complexes of chordal graphs
• Complexes of graphs with bounded matching size
• Bounds on the number of vertex independent sets in a graph
• Tighter bounds on the independence number of the Birkhoff graph
• Independence complexes of stable Kneser graphs

Cites work

• D-collapsibility is NP-complete for d 4
• A simple proof of the upper bound theorem
• A topological colorful Helly theorem
• Choice functions in the intersection of matroids
• d-collapsing and nerves of families of convex sets
• Dimension gaps between representability and collapsibility
• Extremal problems related to Betti numbers of flag complexes
• scientific article; zbMATH DE number 6470115 (Why is no real title available?)
• Large rainbow matchings in general graphs
• Note on a combinatorial application of Alexander duality
• Rainbow fractional matchings
• Rainbow matchings in r-partite r-graphs
• Rainbow matchings in bipartite multigraphs

Cited in

(14)

• Complexes of not i-connected graphs
• Leray numbers of complexes of graphs with bounded matching number
• Noncover complexes, independence complexes, and domination numbers of hypergraphs
• A system of disjoint representatives of line segments with given \(k\) directions
• Collapsibility of non-cover complexes of graphs
• Independence complexes of claw-free graphs
• Rainbow Odd Cycles
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• Inclusion-exclusion formulas from independent complexes
• Complexes of graphs with bounded independence number
• Independence complexes of \((n \times 4)\) and \((n \times 5)\)-grid graphs
• Total cut complexes of graphs
• Rainbow independent sets on dense graph classes
• Inclusion-exclusion formulas from independent complexes

This page was built for publication: Complexes of graphs with bounded independence number

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