Complexes of graphs with bounded independence number

zbMATH Open1447.05246arXiv1912.12605MaRDI QIDQ5918951FDOQ5918951

Authors: Min-Ki Kim, Alan Lew 

Publication date: 14 September 2020

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

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$.

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

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

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

zbMATH Keywords

rainbow independent setshomology\(d\)-collapsibility

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)