Séminaire Lotharingien de Combinatoire, 84B.39 (2020), 12 pp.
Minki Kim and Alan Lew
Complexes of Graphs with Bounded Independence Number
Abstract.
Let G=(V,E) be a graph and n a positive integer. Let In(G) be
the 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 In(G) for various classes
of graphs, focusing on the class of graphs with maximum degree bounded
by Δ. As an application, we obtain the following result:
Let G be a claw-free graph with maximum degree at most
Δ. Then, every collection of
⌊(Δ/2+1)(n-1)⌋+1
independent sets of size n in G has a rainbow independent set of size n.
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: