2010年8月
Independence complexes of chordal graphs
DISCRETE MATHEMATICS
- 巻
- 310
- 号
- 15-16
- 開始ページ
- 2204
- 終了ページ
- 2211
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.disc.2010.04.021
- 出版者・発行元
- ELSEVIER SCIENCE BV
We show that the independence complex l(G) of an arbitrary chordal graph G is either contractible or is homotopy equivalent to the finite wedge of spheres of dimension at least the domination number of G minus 1. Also it is shown that every finite wedge of spheres (as well as a singleton) is realized as the homotopy type of the independence complex of a chordal graph. A combinatorial consequence is a verification of a conjecture due to Aharoni et al. [2, Conjecture 2.4] for chordal graphs. (C) 2010 Elsevier B.V. All rights reserved.
- リンク情報
- ID情報
-
- DOI : 10.1016/j.disc.2010.04.021
- ISSN : 0012-365X
- Web of Science ID : WOS:000279229100016