Independence complexes of strongly orderable graphs

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

1. 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
2. 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
3. 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
4. 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).
5. Dahlhaus, E., Generalized strongly chordal graphs, Technical Report, Basser Department of Computer Science, University of Sydney, 1993, 15 pp.
6. 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
7. 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
8. 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

9. 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
10. 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
11. Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
12. Kawamura, K., Independence complexes of chordal graphs, Discrete Math., 310 (2009), 2204–2211. https://doi.org/10.1016/j.disc.2010.04.021
13. Marietti, M., Testa, D., A uniform approach to complexes arising from forests, Electron. J. Comb., 15 (2008). https://doi.org/10.37236/825
14. 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
15. 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