Independence complexes of strongly orderable graphs
We prove that for any finite strongly orderable (generalized strongly chordal) graph G, the independence complex Ind(G) is either contractible or homotopy equivalent to a wedge of spheres of dimension at least bp(G)−1, where bp(G) is the biclique vertex partition number of G. In particular, we show that if G is a chordal bipartite graph, then Ind(G) is either contractible or homotopy equivalent to a sphere of dimension at least bp(G) − 1.
Keywords:
Independence complex, strongly orderable, strongly chordal, chordal bipartite, convex bipartite, homotopy type biclique vertex partition,
___
- Adamaszek, M., Splittings of independence complexes and the powers of cycles, J. Comb. Theory Ser. A., 119(5) (2012), 1031–1047. https://doi.org/10.1016/j.jcta.2012.01.009
- Bjorner, A., Wachs, M., Shellable nonpure complexes and posets. I, Trans. Amer. Math. Soc., 348(4) (1996), 1299–1327. https://doi.org/10.1090/s0002-9947-96-01534-6
- Bıyıkoglu, T., Civan, Y., Vertex decomposable graphs, codismantlability, Cohen–Macaulayness and Castelnuovo–Mumford regularity, Electron. J. Combin., 21(1) (2014). https://doi.org/10.37236/2387
- Civan, Y., Deniz, Z., Yetim, M. A., Chordal bipartite graphs, biclique vertex partitions and Castelnuovo-Mumford regularity of 1-subdivison graphs, Manuscript in preparation (2021).
- Dahlhaus, E., Generalized strongly chordal graphs, Technical Report, Basser Department of Computer Science, University of Sydney, 1993, 15 pp.
- Dragan, F. F., Strongly orderable graphs A common generalization of strongly chordal and chordal bipartite graphs, Discrete Appl. Math., 99 (1-3) (2000), 427–442. https://doi.org/10.1016/S0166-218X(99)00149-3
- Duginov, O., Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs, Discrete Math. Theor. Comput. Sci., 16(3) (2014), 203–214. https://doi.org/10.46298/dmtcs.2090
- Ehrenborg, R., Hetyei, G., The topology of the independence complex, European J. Combin., 27(6) (2006), 906–923. https://doi.org/10.1016/j.ejc.2005.04.010
- Engstrom, A., Complexes of directed trees and independence complexes, Discrete Math., 309 (2009), 3299–3309. https://doi.org/10.1016/j.disc.2008.09.033
- Farber, M., Characterizations of strongly chordal graphs, Discrete Math., 43(2-3) (1983),173–189. https://doi.org/10.1016/0012-365X(83)90154-1
- Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
- Kawamura, K., Independence complexes of chordal graphs, Discrete Math., 310 (2009), 2204–2211. https://doi.org/10.1016/j.disc.2010.04.021
- Marietti, M., Testa, D., A uniform approach to complexes arising from forests, Electron. J. Comb., 15 (2008). https://doi.org/10.37236/825
- Nagel, U., Reiner, V., Betti numbers of monomial ideals and shifted skew shapes, Electron. J. Comb., 16(2) (2009). https://doi.org/10.37236/69
- Uehara, R., Linear time algorithms on chordal bipartite and strongly chordal graphs, In:Automata, Languages and Programming, Lecture Notes in Computer Science, Volume 2380, Springer, 2002, pp. 993–1004. https://doi.org/10.1007/3-540-45465-9 85
- ISSN: 1303-5991
- Yayın Aralığı: Yılda 4 Sayı
- Başlangıç: 1948
- Yayıncı: Ankara Üniversitesi
Sayıdaki Diğer Makaleler
Zeynep KAYAR, Billur KAYMAKÇALAN
Bibhakar KODAMASİNGH, Muhammad TARİQ, Jamshed NASİR, Soubhagya SAHOO
Gizem YILDIRIM, Selahattin KAÇIRANLAR, Hasan YILDIRIM
Approximation by Szasz-Mirakjan-Durrmeyer operators based on shape parameter $\lambda$
Quaternionic Bertrand curves according to type 2-quaternionic frame in $\mathbb{R}^{4}$