<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Four-Cycled Graphs with Topological Applications
Türker Bıyıkoglu1 and Yusuf Civan2
1Department of Mathematics, Is¸ik University, S¸ ile 34980, Istanbul, Turkey
2Department of Mathematics, Suleyman Demirel University, Isparta 32260, Turkey
Annals of Combinatorics 16 (1) pp.37-56 March, 2012
AMS Subject Classification: 57Q10, 05C38; 05C75
We call a simple graph G a 4-cycled graph if either it has no edges or every edge of it is contained in an induced 4-cycle of G. Our interest on 4-cycled graphs is motivated by the fact that their clique complexes play an important role in the simple-homotopy theory of simplicial complexes. We prove that the minimal simple models within the category of flag simplicial complexes are exactly the clique complexes of some 4-cycled graphs. We further provide structural properties of 4-cycled graphs and describe constructions yielding such graphs. We characterize 4-cycled cographs, and 4-cycled graphs arising from finite chessboards. We introduce
a family of inductively constructed graphs, the external extensions, related to an arbitrary graph, and determine the homotopy type of the independence complexes of external extensions of some graphs.
Keywords: clique and independence complexes, cycled graph, cograph, chessboard graph, simple-homotopy, s-homotopy


1. Barmak, J.A., Minian, E.G.: Minimal finite models. J. Homotopy Relat. Struct. 2(1), 127–140 (2007)

2. Barmak, J.A., Minian, E.G.: Simple homotopy types and finite spaces. Adv. Math. 218(1), 87–104 (2008)

3. Boulet, R., Fieux, E., Jouve, B.: Simplicial simple homotopy of flag complexes in terms of graphs. European J. Combin. 31(1), 161–176 (2010)

4. Brandst¨adt, A., Le, B.V., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (1999)

5. Cohen, M.M.: A Course in Simple-Homotopy Theory. Springer-Verlag, New York (1973)

6. Corneil, D.G., Lerchs, H., Burlingham, L.S.: Complement reducible graphs. Discrete Appl. Math., 3(3), 163–174 (1981)

7. Dochtermann, A., Engström, A.: Algebraic properties of edge ideals via combinatorial topology. Electronic J. Combin. 16(2), #R2 (2009)

8. Ehrenborg, R., Hetyei, G.: The topology of the independence complex. European J. Combin. 27(6), 906–923 (2006)

9. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001)

10. Kozlov, D.: Combinatorial Algebraic Topology. Springer, Berlin (2008)

11. Marietti, M., Testa, D.: Cores of simplicial complexes. Discrete Comput. Geom. 40(3), 444–468 (2008)

12. Lov´asz, L.: Kneser’s conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A 25(3), 319–324 (1978)

13. Villarreal, R.H.: Cohen-Macaulay graphs. Manuscripta Math. 66(3), 277–293 (1990)

14. Wachs, M.L.: Topology of matching, chessboard, and general bounded degree graph complexes. Algebra Universalis 49(4), 345–385 (2003)