Research Article
PDF Mendeley EndNote BibTex Cite

Year 2022, Volume 71, Issue 2, 445 - 455, 30.06.2022
https://doi.org/10.31801/cfsuasmas.874855

Abstract

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

Independence complexes of strongly orderable graphs

Year 2022, Volume 71, Issue 2, 445 - 455, 30.06.2022
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.

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

Details

Primary Language English
Subjects Mathematics
Journal Section Research Articles
Authors

Mehmet Akif YETİM (Primary Author)
SULEYMAN DEMIREL UNIVERSITY
0000-0002-3482-5137
Türkiye

Publication Date June 30, 2022
Application Date February 5, 2021
Acceptance Date December 11, 2021
Published in Issue Year 2022, Volume 71, Issue 2

Cite

Bibtex @research article { cfsuasmas874855, journal = {Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics}, issn = {1303-5991}, eissn = {2618-6470}, address = {Communications Dergi Editörlüğü Ankara Universitesi Fen Fakültesi 06100 Tandoğan ANKARA}, publisher = {Ankara University}, year = {2022}, volume = {71}, number = {2}, pages = {445 - 455}, doi = {10.31801/cfsuasmas.874855}, title = {Independence complexes of strongly orderable graphs}, key = {cite}, author = {Yetim, Mehmet Akif} }
APA Yetim, M. A. (2022). Independence complexes of strongly orderable graphs . Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics , 71 (2) , 445-455 . DOI: 10.31801/cfsuasmas.874855
MLA Yetim, M. A. "Independence complexes of strongly orderable graphs" . Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics 71 (2022 ): 445-455 <https://dergipark.org.tr/en/pub/cfsuasmas/issue/69957/874855>
Chicago Yetim, M. A. "Independence complexes of strongly orderable graphs". Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics 71 (2022 ): 445-455
RIS TY - JOUR T1 - Independence complexes of strongly orderable graphs AU - Mehmet Akif Yetim Y1 - 2022 PY - 2022 N1 - doi: 10.31801/cfsuasmas.874855 DO - 10.31801/cfsuasmas.874855 T2 - Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics JF - Journal JO - JOR SP - 445 EP - 455 VL - 71 IS - 2 SN - 1303-5991-2618-6470 M3 - doi: 10.31801/cfsuasmas.874855 UR - https://doi.org/10.31801/cfsuasmas.874855 Y2 - 2021 ER -
EndNote %0 Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics Independence complexes of strongly orderable graphs %A Mehmet Akif Yetim %T Independence complexes of strongly orderable graphs %D 2022 %J Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics %P 1303-5991-2618-6470 %V 71 %N 2 %R doi: 10.31801/cfsuasmas.874855 %U 10.31801/cfsuasmas.874855
ISNAD Yetim, Mehmet Akif . "Independence complexes of strongly orderable graphs". Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics 71 / 2 (June 2022): 445-455 . https://doi.org/10.31801/cfsuasmas.874855
AMA Yetim M. A. Independence complexes of strongly orderable graphs. Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat.. 2022; 71(2): 445-455.
Vancouver Yetim M. A. Independence complexes of strongly orderable graphs. Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics. 2022; 71(2): 445-455.
IEEE M. A. Yetim , "Independence complexes of strongly orderable graphs", Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics, vol. 71, no. 2, pp. 445-455, Jun. 2022, doi:10.31801/cfsuasmas.874855

Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics.

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.