Independence complexes of strongly orderable graphs

Year 2022, Volume: 71 Issue: 2, 445 - 455, 30.06.2022

Mehmet Akif Yetim

https://doi.org/10.31801/cfsuasmas.874855

Abstract

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

References

• 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