Independence complexes of claw-free graphs
2008 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 29, no 1, 234-241 p.Article in journal (Refereed) Published
We study the class of independence complexes of claw-free graphs. The main theorem gives good bounds on the connectivity of these complexes, given bounds for a few subcomplexes of the same class. Two applications are presented. Firstly, we show that the independence complex of a claw-free graph with n vertices and maximal degree d is (cn/d + epsilon)-connected, where c = 2/3. This can be compared with the result of Szabo and Tardos that c = 1/2 is optimal with no restrictions on the graphs. Secondly, we calculate the connectivity of a family of complexes used in Babson and Kozlov's proof of the Lovasz conjecture.
Place, publisher, year, edition, pages
2008. Vol. 29, no 1, 234-241 p.
IdentifiersURN: urn:nbn:se:kth:diva-10371DOI: 10.1016/j.ejc.2006.09.007ISI: 000251166600022ScopusID: 2-s2.0-35548987051OAI: oai:DiVA.org:kth-10371DiVA: diva2:216351
QC 201007122009-05-082009-05-082011-11-07Bibliographically approved