Collapsibility bound for independence complexes of bounded-degree graphs
Collapsibility bound for independence complexes of bounded-degree graphs
Let be a graph, and let denote its complex of independent sets of size at most . For a simplicial complex , let denote its collapsibility number. Let be a nonnegative integer and let be a positive integer.
Collapsibility conjecture. If has maximum degree at most , then
This is proposed as an extension of the Aharoni–Briggs–Kim–Kim conjecture. The bound is known for claw-free graphs, but the paper gives counterexamples in general, so the conjecture is refuted.
Sources & referencesView supporting material
Primary source
Minki Kim and Alan Lew, “Complexes of graphs with bounded independence number”, arXiv:1912.12605 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.