TY - JOUR
T1 - Complexes of graphs with bounded matching size
AU - Linusson, Svante
AU - Shareshian, John
AU - Welker, Volkmar
PY - 2008/5
Y1 - 2008/5
N2 - For positive integers k,n, we investigate the simplicial complex NM k(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex BNMk(r,s) of all bipartite graphs G on bipartition [r]∪[s̄] such that there is no matching of size k in G, and obtain results similar to those obtained for NMk(n).
AB - For positive integers k,n, we investigate the simplicial complex NM k(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r,s and k the simplicial complex BNMk(r,s) of all bipartite graphs G on bipartition [r]∪[s̄] such that there is no matching of size k in G, and obtain results similar to those obtained for NMk(n).
KW - Critical
KW - Gallai-Edmonds
KW - Trees of triangles
UR - https://www.scopus.com/pages/publications/42149171166
U2 - 10.1007/s10801-007-0092-1
DO - 10.1007/s10801-007-0092-1
M3 - Article
AN - SCOPUS:42149171166
SN - 0925-9899
VL - 27
SP - 331
EP - 349
JO - Journal of Algebraic Combinatorics
JF - Journal of Algebraic Combinatorics
IS - 3
ER -